例题 hdu 2544
解法 1.Dijkstra
复杂度为 o(n*n) n 为点的个数
从 1 点开始贪心地寻找最佳距离
可以求出 1 号点到其它点的最短距离
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int maxn=105;
- const int INF=1e9+10;
- bool ins[maxn];
- int ma[maxn][maxn];
- int dis[maxn];
- int n,m;
- void dijkstra()
- {
- memset(ins,0,sizeof(ins));
- for(int i=2;i<=n;i++)
- dis[i]=ma[1][i];
- dis[1]=0;
- ins[1]=1;
- while(1)
- {
- int minn=INF,index;
- for(int i=1;i<=n;i++)
- {
- if(ins[i]==0&&dis[i]<minn)
- {
- minn=dis[i];index=i;
- }
- }
- if(minn==INF)break;
- ins[index]=1;
- for(int i=1;i<=n;i++)
- {
- if(ins[i]==0&&ma[index][i]+dis[index]<dis[i])
- dis[i]=ma[index][i]+dis[index];
- }
- }
- printf("%d\n",dis[n]);
- }
- int main()
- {
- while(scanf("%d %d",&n,&m)==2)
- {
- if(n==0&&m==0)break;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- ma[i][j]=INF;
- for(int i=1;i<=m;i++)
- {
- int a,b,c;
- scanf("%d %d %d",&a,&b,&c);
- ma[a][b]=min(c,ma[a][b]);
- ma[b][a]=min(c,ma[b][a]);
- }
- dijkstra();
- }
- return 0;
- }
解法 2.Floyd
复杂度 o(n*n*n)
每次插入 1 个点, 更新整个矩阵
可以求出两两之间的最短路径
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int INF=1e9+10;
- const int maxn=105;
- int ma[maxn][maxn];
- int n,m;
- void floyd()
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- for(int k=1;k<=n;k++)
- ma[j][k]=min(ma[j][k],ma[j][i]+ma[i][k]);
- }
- printf("%d\n",ma[1][n]);
- }
- int main()
- {
- while(scanf("%d %d",&n,&m)==2)
- {
- if(n==0&&m==0)break;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- ma[i][j]=INF;
- for(int i=1;i<=m;i++)
- {
- int a,b,c;
- scanf("%d %d %d",&a,&b,&c);
- ma[a][b]=min(ma[a][b],c);
- ma[b][a]=min(ma[b][a],c);
- }
- floyd();
- }
- return 0;
- }
解法 3.SPFA
复杂度 o(n*v) v 为图中边的个数
贪心从 1 点寻找最短距离
优点是可以计算带有负边的图, 缺点, 复杂度高
- #include<iostream>
- #include<cstdio>
- #include<queue>
- using namespace std;
- const int maxn=110;
- const int INF=1e9+10;
- int ma[maxn][maxn],dis[maxn];
- bool ins[maxn];
- int n,m;
- struct Node{
- int x;
- bool operator <(const Node &a)const
- {
- return dis[x]<dis[a.x];
- }
- Node(int a)
- {
- x=a;
- }
- };
- void spfa()
- {
- for(int i=1;i<=n;i++)ins[i]=0;
- priority_queue<Node>que;
- for(int i=1;i<=n;i++)
- dis[i]=INF;
- dis[1]=0;
- que.push(Node(1));
- while(que.size())
- {
- int x=que.top().x;
- que.pop();
- ins[x]=0;
- for(int i=1;i<=n;i++)
- {
- if(dis[i]>dis[x]+ma[x][i])
- {
- dis[i]=dis[x]+ma[x][i];
- if(ins[i]==0)
- {
- ins[i]=1;
- que.push(Node(i));
- }
- }
- }
- }
- printf("%d\n",dis[n]);
- }
- int main()
- {
- while(scanf("%d %d",&n,&m)==2)
- {
- if(n==0&&m==0)break;
- for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ma[i][j]=INF;
- for(int i=1;i<=m;i++)
- {
- int a,b,c;
- scanf("%d %d %d",&a,&b,&c);
- ma[a][b]=min(ma[a][b],c);
- ma[b][a]=min(ma[b][a],c);
- }
- spfa();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2619298.html