春游
春天阳光灿烂，小宋突然心血来潮想骑自行车去学校外面玩，但是到达目的地的路线不止一条，他想尽快的到达目的地，又能不需要骑太远的路， 你能帮助他吗？
输入格式:
输入包含一个测试数据，第一行有三个整数n(2 <= n <= 1000)，途中可能经过的地点的个数，地点编号1~n；m(1 <= m <= 10000)，为路径的条数；d(2 <= d <= n)，目的地编号；其中学校为起点，默认为1。接下来m行： x y time dist ， x y表示地点x，y是可以相互到达的，time，dist分别表示x到y或y到x的时间，距离。
输出格式:
按如下格式输出“花费的时间+空格+要骑的距离+空格+从学校到达目的地的路径”，路径中的两个地点之间以箭头（->）分隔。（具体见输出样例）
输入样例:
7 8 7
1 2 1 1
1 3 1 1
2 4 1 2
3 4 1 1
4 5 1 2
4 6 1 1
5 7 1 1
6 7 2 1
输出样例:
4 5 1->3->4->5->7
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 100000
int n;
int tu[1005][1005];
int len[1005][1005];
int vist[1005];
int tim[1005];
int dist[1005];
int path[1005];
void dijkstra(){
while(1){
int min=INF,x=-1;
for(int i=1;i<n+1;i++){
if(vist[i]!=1&&tim[i]<min){
min=tim[i];
x=i;
}
}
if(x==-1) break;
vist[x]=1;
for(int i=1;i<n+1;i++){
if(vist[i]||!tu[x][i]) continue;
if(tim[i]>tim[x]+tu[x][i]){
tim[i]=tim[x]+tu[x][i];
dist[i]=dist[x]+len[x][i];
path[i]=x;
}
else if(tim[i]==tim[x]+tu[x][i]){
if(dist[i]>dist[x]+len[x][i]){
dist[i]=dist[x]+len[x][i];
path[i]=x;
}
}
}
}
}
int main(){
int m;int end;
cin>>n>>m>>end;
while(m--){
int a,b,c,d;
cin>>a>>b>>c>>d;
tu[a][b]=c;tu[b][a]=c;
len[a][b]=d;len[b][a]=d;
}
fill(tim,tim+1005,INF);
fill(dist,dist+1005,INF);
fill(path,path+1005,-1);
tim[1]=0;dist[1]=0;
dijkstra();
cout<<tim[end]<<" "<<dist[end]<<" ";
int f[n];int k=1;f[0]=end;
while(path[end]!=-1){
end=path[end];
f[k++]=end;
}
int flag=0;
while(k--) {
if(flag)printf("->");
printf("%d",f[k]);
flag=1;
}
}
oj的结果是
