hdu 3790 最短路径问题(Dijkstra)

题目：​​#include#includeusing namespace std;int n;const int INF=0x3f3f3f3f;int map[1005][1005],cost[1005][1005],dis[1005],spe[1005];void inital(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cost[i][j]=INF; map[i][j]=INF; } }}void Dijkstra(int s,int t){ bool tag[1005]; memset(tag,0,sizeof(tag)); memset(dis,0,sizeof(dis)); memset(spe,0,sizeof(spe)); tag[s]=1; dis[s]=0; for(int i=1;i<=n;i++){ dis[i]=map[s][i]; spe[i]=cost[s][i]; } for(int i=1;idis[j]){ mmin=dis[j]; minsp=spe[j]; k=j; } } if(k==0)return ; tag[k]=1; for(int j=1;j<=n;j++){ if(!tag[j]&&map[k][j]!=INF){ if(dis[j]>mmin+map[k][j]){ //spe跟着变 dis[j]=mmin+map[k][j]; spe[j]=minsp+cost[k][j]; } else if(dis[j]==mmin+map[k][j]&&spe[j]>minsp+cost[k][j]){ spe[j]=minsp+cost[k][j]; } } } }}int main(){ //freopen("cin.txt","r",stdin); int m,i,j,s,t; while(cin>>n>>m){ if(n==0&&m==0)break; inital(); for(i=0;ip){ //担心又有奇葩数据~ cost[a][b]=p; cost[b][a]=p; } else if(map[a][b]>d){ map[a][b]=d; map[b][a]=d; cost[a][b]=p; cost[b][a]=p; } } scanf("%d%d",&s,&t); Dijkstra(s,t); printf("%d %d\n",dis[t],spe[t]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。