hdu3790 最短路径问题

Problem Description 给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
Input 输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
Output 输出一行有两个数，最短距离及其花费。
Sample Input

Sample Output

9 11

Source 浙大计算机研究生复试上机考试-2010年用cin读入，会超时。。。

#include<iostream>
using namespace std;

#define inf 0xffffff

int map[1005][1005],dis[1005],vis[1005],path[1005],cost[1005][1005],value[1005];
//map存两点距离，dis存最短距离，vis标记，path存路径,cost存两点间发费，value存发费 
int sum;

void Dijkstra(int n,int x){
int i,j,k,min;
for(i=1;i<=n;i++){
dis[i]=map[x][i];
vis[i]=0;
value[i]=cost[x][i];
}
vis[x]=1;
for(i=1;i<=n;i++){
min=inf;
for(j=1;j<=n;j++){
if(!vis[j]&&dis[j]<min){
k=j;
min=dis[j];
}
}
vis[k]=1;
for(j=1;j<=n;j++){
if(!vis[j] && dis[k]+map[k][j]<dis[j]){
dis[j]=dis[k]+map[k][j];
value[j]=value[k]+cost[k][j];
}
else if(dis[j]==dis[k]+map[k][j]){
if(value[j]>value[k]+cost[k][j])
value[j]=value[k]+cost[k][j];
}
}
}

}

int main(){
int n,m,i,j,k,x,y,p,q;
while(cin>>n>>m&&(m+n)){
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
map[i][j]=inf;
cost[i][j]=inf;
}

for(i=1;i<=m;i++){
scanf("%d%d%d%d",&x,&y,&p,&q);
if(map[x][y]>p){
map[x][y]=map[y][x]=p;
cost[x][y]=cost[y][x]=q;
}
else if(map[x][y]==p){
if(cost[x][y]>q)
cost[x][y]=cost[y][x]=q;
}
}
scanf("%d%d",&i,&j);
Dijkstra(n,i);
sum=0;
cout<<dis[j]<<" "<<value[j]<<endl;
}
return 0;
}

秒客网

hdu3790 最短路径问题

相关文章