输入样例:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
结尾无空行

输出样例:

3 40
结尾无空行

代码

#include<iostream>
#define INFINITY 65535
using namespace std;
int edges[505][505];
int price[505][505];
int N;
void Dijkstra(int begin,int end)
{int v,w,k,min;int final[505],D[505];int Cost[505];for(v=0;v<N;v++){final[v]=0;D[v]=edges[begin][v];Cost[v]=price[begin][v];}D[begin]=0;Cost[begin]=0;final[begin]=1;for(v=1;v<N;v++){min=INFINITY;//找到所知离begin顶点的最近距离 for(w=0;w<N;w++){if(!final[w]&&D[w]<min){k=w;min=D[w];}}final[k]=1;for(w=0;w<N;w++){//如果经过k顶点的路径比原路径更短，则更新if(!final[w]&&(min+edges[k][w])<D[w]){D[w]=min+edges[k][w];//cout<<k<<" "<<w<<" "<<min<<" "<<edges[k][w]<<" "<<D[w]<<endl;Cost[w]=Cost[k]+price[k][w];}if(!final[w]&&(min+edges[k][w])==D[w]&&(Cost[k]+price[k][w])<Cost[w]){D[w]=min+edges[k][w];Cost[w]=Cost[k]+price[k][w];}}}cout<<D[end]<<" "<<Cost[end]<<endl;
}
int main()
{int M,S,D;cin>>N>>M>>S>>D;for(int i=0;i<N;i++){for(int j=0;j<N;j++){if(i==j) {edges[i][j]=0;price[i][j]=0;}else {edges[i][j]=INFINITY;price[i][j]=INFINITY;}}}for(int i=0;i<M;i++){int va,vb,len,cost;cin>>va>>vb>>len>>cost;edges[va][vb]=edges[vb][va]=len;price[va][vb]=price[vb][va]=cost;}Dijkstra(S,D);return 0;
}