nyoj 115 城市平乱（Dijkstra算法求解）

绝地灬酷狼 2024-02-17 19:59 37阅读 0赞

### 城市平乱 ###

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 4

描述

南将军统领着N个部队，这N个部队分别驻扎在N个不同的城市。

他在用这N个部队维护着M个城市的治安，这M个城市分别编号从1到M。

现在，小工军师告诉南将军，第K号城市发生了暴乱，南将军从各个部队都派遣了一个分队沿最近路去往暴乱城市平乱。

现在已知在任意两个城市之间的路行军所需的时间，你作为南将军麾下最厉害的程序员，请你编写一个程序来告诉南将军第一个分队到达叛乱城市所需的时间。

![20101122174626_27048.png][]

注意，两个城市之间可能不只一条路。

输入

第一行输入一个整数T，表示测试数据的组数。(T<20)  
每组测试数据的第一行是四个整数N,M,P,Q(1<=N<=100,N<=M<=1000,M-1<=P<=100000)其中N表示部队数，M表示城市数，P表示城市之间的路的条数,Q表示发生暴乱的城市编号。  
随后的一行是N个整数，表示部队所在城市的编号。  
再之后的P行，每行有三个正整数，a,b,t(1<=a,b<=M,1<=t<=100)，表示a,b之间的路如果行军需要用时为t  
  
数据保证暴乱的城市是可达的。

输出

对于每组测试数据，输出第一支部队到达叛乱城市时的时间。每组输出占一行

样例输入

1
    3 8 9 8
    1 2 3
    1 2 1
    2 3 2
    1 4 2
    2 5 3
    3 6 2
    4 7 1
    5 7 3
    5 8 2
    6 8 2

样例输出

分析：最短路径问题，可用Dijkstra算法求解，本题我用的是他的 mlogn复杂度算法求解。（纯模板题）

AC代码：

#include<cstdio>
    #include<cstring>
    #include<vector>
    #include<queue>
    #include<algorithm>
    using namespace std;
    #define INF 10000000+10;
    const int maxn=1000+3;
    struct Edges{
    	int from,to,dist;
    	Edges(int from,int to,int dist):from(from),to(to),dist(dist){}
    };
    
    struct node{
    	int dt,u;
    	node(int dt,int u):dt(dt),u(u){}
    	bool operator<(const node& nd)const{
    	return dt>nd.dt;
    	}
    };
    
    vector<Edges>edges;
    vector<int>G[maxn];
    int cnt[100+2];
    int N,M,P,Q;
    int vis[maxn];
    int d[maxn];
    
    int dijkstra(int s){
    	memset(vis,0,sizeof(vis));
    	for(int i=1;i<=M;i++)d[i]=INF;
    	d[s]=0;
    	priority_queue<node>q;
    	q.push(node(0,s));
    	while(!q.empty()){
    		node v=q.top();
    		q.pop();
    		
    		int u=v.u;
    		if(u==Q)return d[u];
    		if(vis[u])continue;
    		vis[u]=1;
    		
    		for(int i=0;i<G[u].size();i++){
    			Edges e=edges[G[u][i]];
    			if(d[e.to]>d[e.from]+e.dist){
    				d[e.to]=d[e.from]+e.dist;
    				q.push(node(d[e.to],e.to));
    			}
    		}
    	}
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d%d%d",&N,&M,&P,&Q);
    		for(int i=0;i<N;i++)
    		scanf("%d",&cnt[i]);
    		
    		for(int i=0;i<P;i++){
    			int from,to,dist;
    			scanf("%d%d%d",&from,&to,&dist);
    			edges.push_back(Edges(from,to,dist));
    			int len=edges.size();
    			edges.push_back(Edges(to,from,dist));
    			G[from].push_back(len-1);
    			G[to].push_back(len);
    		}
    		
    		int tmp=INF;
    		for(int i=0;i<N;i++){
    			tmp=min(tmp,dijkstra(cnt[i]));
    		}
    		
    		printf("%d\n",tmp);
    		
    		for(int i=0;i<M;i++)G[i].clear();
    		edges.clear();
    	}
    	return 0;
    }

[20101122174626_27048.png]: http://acm.nyist.net/JudgeOnline/admin/kind/attached/20101122174626_27048.png