hdu3790 最短路径问题

时间:2022-02-27 09:41:52

hdu3790

注意:1.有重边的情况。

            2.要判断两种情况,路径相同时判断花费的多少。

#include<stdio.h>
#include <iostream>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<list>
#include<vector>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define INF 1000000
#define MAX 1005

int main()
{
int dis[MAX],cost[MAX][MAX],visit[MAX],map[MAX][MAX],cos[MAX];
int n,m;
int a,b,d,p;
int i,j,s,t,min,pre,k;
while(scanf("%d%d",&n,&m),n||m)
{
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
map[i][j]=INF;
cost[i][j]=INF;
}
}
for(i=0;i<MAX;i++)
{
visit[i]=0;
}
for (i=0;i<m;i++)
{
scanf("%d%d%d%d",&a,&b,&d,&p);
if(d<map[a][b])
{
map[a][b]=map[b][a]=d;
cost[a][b]=cost[b][a]=p;
}
else if(d==map[a][b] && p<cost[a][b])
{
cost[a][b]=cost[b][a]=p;
}
}
scanf("%d%d",&s,&t);
visit[s]=1;
for (j=1;j<=n;j++)
{
dis[j]=map[s][j];
cos[j]=cost[s][j];
}
for (i=1;i<=n;i++)
{
min=INF;
for (j=1;j<=n;j++)
{
if(!visit[j] && min>dis[j])
{
min=dis[j];
pre=j;
}
}
visit[pre]=1;

for (k=1;k<=n;k++)
{
if(!visit[k] && dis[k] > dis[pre]+map[pre][k])
{
dis[k]=dis[pre]+map[pre][k];
cos[k]=cos[pre]+cost[pre][k];
}
else
if(!visit[k]&&dis[k]==dis[pre]+map[pre][k]&&cos[k]>cos[pre]+cost[pre][k])//路径相同时判断花费的多少
{
cos[k]=cos[pre]+cost[pre][k];
}
}
}
printf("%d %d\n",dis[t],cos[t]);
}
return 0;
}