最基础的单源最短路径
dijkstra 复杂度O(n^2)
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 50100 #define eps 1e-7 #define INF 0x7FFFFFFF #define long long ll; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int edge[110][110]; int vis[110]; int dist[110]; int n,m; void dijkstra(int v){ int i,j; for(i=1;i<=n;i++){ dist[i] = edge[v][i]; } vis[v] = 1; for(i=0;i<n-1;i++){ int temp = INF; int k = -1; for(j=1;j<=n;j++){ if(!vis[j]&&dist[j]<temp){ temp = dist[j]; k = j; } } if(k==-1) break; vis[k] = 1; for(j=1;j<=n;j++){ if(!vis[j]&&dist[k]!=INF&&edge[k][j]!=INF&&dist[j]>dist[k]+edge[k][j]) dist[j] = dist[k] + edge[k][j]; } } } int main(){ int i,j,a,b,c; while(scanf("%d%d",&n,&m),n||m){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ edge[i][j] = INF; } } memset(vis,0,sizeof(vis)); for(i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); edge[a][b] = edge[b][a] = c; } dijkstra(1); printf("%d\n",dist[n]); } return 0; }
Floyd 复杂度O(n^3)
#include<stdio.h> #include<cstring> #include<algorithm> #include<math.h> #include<iostream> using namespace std; int main() { int n,m,a[105][105],i,j,k,x,y,t; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) return 0; memset(a,0,sizeof(a)); for(i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&t); a[x][y]=t; a[y][x]=t; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) { if(a[i][j]&&a[i][k]&&(a[j][k]>a[i][j]+a[i][k]||a[j][k]==0)) a[j][k]=a[i][j]+a[i][k]; } printf("%d\n",a[1][n]); } return 0; }