HDU 2544 最短路（单源最短路）

╰半橙微兮° 2024-02-17 19:43 74阅读 0赞

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。  
输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 1
    1 2 3
    3 3
    1 2 5
    2 3 5
    3 1 2
    0 0

Sample Output

3
    2

分析：单源最短路，Dijkstra算法（n^2复杂度）

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 2147483647
    const int maxn=100+10;
    int d[maxn];
    int vis[maxn];
    int g[maxn][maxn];
    int main(){
    	int n,m;
    	while(scanf("%d%d",&n,&m)==2 && n){
    		memset(g,0,sizeof(g));
    		for(int i=0;i<m;i++){
    			int a,b,c;
    			scanf("%d%d%d",&a,&b,&c);
    			g[a][b]=g[b][a]=c;
    		}
    		
    		memset(vis,0,sizeof(vis));
    		d[1]=0;
    		for(int i=2;i<=n;i++)d[i]=INF;
    		for(int i=1;i<=n;i++){
    			int x,m=INF;
    			for(int y=1;y<=n;y++)if(!vis[y] && d[y]<=m)
    			m=d[x=y];
    			
    		    vis[x]=1;
    		    for(int y=1;y<=n;y++)
    		    if(g[x][y])
    		    d[y]=min(d[y],d[x]+g[x][y]);
    		}
    		
    		printf("%d\n",d[n]);
    	}
    	return 0;
    }

解法二：Dijkstra之（mlogn复杂度）

AC代码：

#include<cstdio>
    #include<cstring>
    #include<vector>
    #include<queue>
    #include<algorithm>
    #define INF 10000000+1
    using namespace std;
    const int maxn=100+5;
    int d[maxn],done[maxn];
    int n,m;
    struct Edge{
    	int from,to,dist;
    	Edge(int from,int to,int dist):from(from),to(to),dist(dist){}
    };
    
    struct node{
    	int d1,u;
    	node(int d1,int u):d1(d1),u(u){}
    	bool operator<(const node& nd)const{
    	return d1>nd.d1;    //这里不要写成了< !! 
    	}
    };
    vector<Edge>edges;
    vector<int>G[maxn];
    
    void init(){
    	for(int i=1;i<=n;i++)G[i].clear();
    	edges.clear();
    }
    
    void dijkstra(){
    	priority_queue<node>q;
    	for(int i=1;i<=n;i++)d[i]=INF;
    	d[1]=0;
    	memset(done,0,sizeof(done));
    	q.push(node(0,1));
    	while(!q.empty()){
    		node v=q.top();
    		q.pop();
    		
    		int u=v.u;
    		if(u==n)return ;
    		if(done[u])continue;
    		done[u]=1;
    		for(int i=0;i<G[u].size();i++){
    			Edge& 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(){
    	while(scanf("%d%d",&n,&m)==2 && n){
    		for(int i=0;i<m;i++){
    			int A,B,C;
    			scanf("%d%d%d",&A,&B,&C);
    			edges.push_back(Edge(A,B,C));
    			int len=edges.size();
    			edges.push_back(Edge(B,A,C));
    			G[A].push_back(len-1);
    			G[B].push_back(len);
    		}
    		
    		dijkstra();
    		printf("%d\n",d[n]);
    		init();
    	}
    	return 0;
    }

解法3：Floyd算法（复杂度n^3），这种算法用的是动态规划的思想，求多源最短路，因为本题数据量比较小，所以可以求解。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 10000000
    const int maxn=100+2;
    int e[maxn][maxn];
    int main(){
    	int n,m;
    	while(scanf("%d%d",&n,&m)==2 && n){
    		for(int i=1;i<=n;i++)
    		 for(int j=1;j<=n;j++)
    		 if(i==j)e[i][j]=0;
    		 else e[i][j]=INF;
    		 
    		 for(int i=0;i<m;i++){
    		 	int  A,B,C;
    		 	scanf("%d%d%d",&A,&B,&C);
    		 	e[A][B]=C;
    		 	e[B][A]=C;
    		 }
    		 
    		 for(int k=1;k<=n;k++)
    		  for(int i=1;i<=n;i++)
    		   for(int j=1;j<=n;j++)
    		   e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
    		   
    		   printf("%d\n",e[1][n]);
    	}
    	return 0;
    }