本文主要是介绍hdu 3790 最短路径问题(Dijkstra)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：http://acm.hdu.edu.cn/showproblem.php?pid=3790
和普通的最短路径相比，这里要多计算相同最短路径下的最小费用，所以再增加一个数组，在Dijkstra里也做一点改动，让费用数组跟着变化。
#include <iostream>
#include<cstdio>
#include<cstring>
using 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;i<n;i++){int k=0,mmin=INF,minsp=INF;for(int j=1;j<=n;j++){if(!tag[j]&&mmin>dis[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;i<m;i++){int a,b,d,p;scanf("%d%d%d%d",&a,&b,&d,&p);if(map[a][b]==d&&cost[a][b]>p){ //担心又有奇葩数据~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;
}
这篇关于hdu 3790 最短路径问题(Dijkstra)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
