2014.网研院.Problem D. 网络传输

悠悠 2023-05-28 05:07 20阅读 0赞

**题目描述**  
网络的高效互联与智能传输是提升海量用户服务请求映射效率的重要措施。在这个任务中，你要用最少的传输时间，将特定的数据源发送到指定的网络节点中。  
我么给定的网络一共包含N个节点（从1到N编号），其中节点1为数据源。网络中有M条无向边（u,v,w），表示一条传输线连接节点u和节点v，且数据通过这条传输线的平均时间为w。由于传送机制的限制，当一个节点接收到数据之后，它只能选择与它互连的一个节点，并将数据转发到该节点。节点1在初始化时只会发送一次数据，但在传输过程中它可以作为转发节点。  
网络中有k个目标节点，你需要计算出该数据从节点1传送到所有K歌节点所需要的最短时间。注意目标节点可以按任意顺序进行传送，数据也可以多次经过同一节点。  
**输入格式**  
输入数据第一行是一个整数T（T<=5），表示测试数据的组数。  
对于每组测试数据：  
第一行是三个正整数N,M,K（2<=N<=1000，1<=M<=N(N-1)/2，K<=10），分别表示节点数，边数和目标节点数。  
接下来M行，每行三个整数u,v,w（1<=u,v<=N, 0<=w<=1000,u!=v）。如上所述给出每条传输线。任意两个网络节点之间最多只会有一条边相连。  
最后一行是K个整数，给出所有的目标节点的编号，所有目标节点的编号都在2到N之间。  
**输出格式**  
对于每组测试数据，输出数据传送到所有K个目标节点的最短时间。  
**样例输入**

2
    3 2 2
    1 3 1
    1 2 3
    2 3
    6 6 4
    1 5 1
    5 6 2
    2 1 20
    2 3 5
    3 4 5
    6 3 1
    2 3 4 6

**样例输出**

5 
    19

**样例说明**  
在第一组样例中，最短路线是：1->3->1->2  
在第二组样例中，最短路线是：1->5->6->3->2->3->4，或者1->5->6->3->4->3->2

#include<bits/stdc++.h>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int maxn = 1005;
    int dis[maxn];
    int g[maxn][maxn];
    int main() { 
    	int T,n,m,kk;
    	int u,v,w;
    	cin>>T;
    	while(T--) { 
    		cin>>n>>m>>kk;
    		memset(g,INF,sizeof(g));
    		for(int i=1;i<=n;i++){ 
    			g[i][i]=0;
    		}
    		while(m--) { 
    			cin>>u>>v>>w;
    			g[u][v]=w;
    			g[v][u]=w;
    		}
    		int num[kk];
    		for(int i=0; i<kk; i++) { 
    			cin>>num[i];
    		}
    		for(int k=1; k<=n; k++) { 
    			for(int i=1; i<=n; i++) { 
    				for(int j=1; j<=n; j++) { 
    					if(g[i][k]+g[k][j]<g[i][j]&&g[i][k]!=INF&&g[k][j]!=INF) { 
    						g[i][j]=g[i][k]+g[k][j];
    					}
    				}
    			}
    		}
    		sort(num,num+kk);
    		int pre,min=INF,sum;
    		do { 
    			sum=0;
    			pre=1;
    			for(int i=0; i<kk; i++) { 
    				sum+=g[pre][num[i]];
    				pre=num[i];
    			}
    			if(sum<min) { 
    				min=sum;
    			}
    		} while(next_permutation(num,num+kk));
    		cout<<min<<endl;
    	}
    	return 0;
    }