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;
}