- 题目描述:
-
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
- 输入:
-
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
- 输出:
-
输出 一行有两个数, 最短距离及其花费。
- 样例输入:
-
3 2
1 2 5 6
2 3 4 5
1 3
0 0
- 样例输出:
-
9 11
#include<stdio.h>
#include<vector>
using namespace std;
struct E{
int next;
int c;
int cost;
};
vector<E> edge[1001];
int dis[1001];
int cost[1001];
bool mark[1001];
int main(){
int n,m;
int s,t;
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0 && m==0) break;
for(int i=1;i<=n;i++){
edge[i].clear();
}
while(m--){
int a,b,c,cost;
scanf("%d%d%d%d",&a,&b,&c,&cost);
E temp;
temp.c=c;
temp.cost=cost;
temp.next=b;
edge[a].push_back(temp);
temp.next=a;
edge[b].push_back(temp);
}
scanf("%d%d",&s,&t);
for(int i=1;i<=n;i++){
dis[i]=-1;
mark[i]=false;
}
dis[s]=0;
mark[s]=true;
int newp=s;
for(int i=1;i<n;i++){
for(int j=0;j<edge[newp].size();j++){
int t=edge[newp][j].next;
int c=edge[newp][j].c;
int co=edge[newp][j].cost;
if(mark[t]==true) continue;
if(dis[t]==-1 || dis[t]>dis[newp]+c || dis[t]==dis[newp]+c && cost[t]>cost[newp]+co){
dis[t]=dis[newp]+c;
cost[t]=cost[newp]+co;
}
}
int min=999999999;
for(int j=1;j<=n;j++){
if(mark[j]==true) continue;
if(dis[j]==-1) continue;
if(dis[j]<min){
min=dis[j];
newp=j;
}
}
mark[newp]=true;
}
printf("%d %d
",dis[t],cost[t]);
}
return 0;
}