中文题,迪杰斯特拉最短路径算法模板题。
#include<stdio.h> #include<string.h> #define INF 0x3f3f3f3f int visit[510],vis[510],map[510][510],low[510],a[510]; int n,m,start,end; void dijkstra() { int min,max,i,j,next; memset(visit,0,sizeof(visit)); visit[start]=1; for(i=0;i<n;i++) { vis[i]=map[start][i]; low[i]=a[start]+a[i]; } low[start]=a[start]; for(i=0;i<n;i++) { min=INF; max=0; for(j=0;j<n;j++)//找到时间最小的 前提时间小 其次是钱多 { if(min>vis[j]&&!visit[j]) { min=vis[j]; next=j; max=low[j]; } if(min==vis[j]&&!visit[j]&&max<low[j]) { next=j; max=low[j]; } } visit[next]=1; for(j=0;j<n;j++)//更新到时间最小 前提时间最小 其次是钱多 { if(!visit[j]&&vis[j]>vis[next]+map[next][j]) { vis[j]=vis[next]+map[next][j]; low[j]=low[next]+a[j]; } if(!visit[j]&&vis[j]==vis[next]+map[next][j]&&low[j]<low[next]+a[j]) low[j]=low[next]+a[j]; } } printf("%d %d ",vis[end],low[end]); } int main() { int i,j,x,y,z; while(~scanf("%d%d%d%d",&n,&m,&start,&end)) { for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) for(j=i;j<n;j++) { if(i==j) map[i][j]=0; else map[i][j]=map[j][i]=INF; } while(m--) { scanf("%d%d%d",&x,&y,&z); if(map[x][y]>z) map[x][y]=map[y][x]=z; } dijkstra(); } return 0; }