- #include<iostream>
- using namespace std;
- #define MAX 9999999
- int map[2005][2005],pay[2005][2005];
- int used[2005],dist[2005],pas[2005];
- int p,q,n;
- int i,j;
- void dijkstra()
- {
- for(i=1;i<=n;i++)
- {
- dist[i]=map[p][i];
- pas[i]=pay[p][i];
- used[i]=0;
- }
- dist[p]=0;
- used[p]=1;
- int num=1;
- while(num<n)
- {
- num++;
- int pos;
- int min=MAX;
- for(i=1;i<=n;i++)
- {
- if(!used[i]&&dist[i]<min)
- {
- min=dist[i];
- pos=i;
- }
- }
- if(min==MAX)
- break;
- used[pos]=1;
- for(i=1;i<=n;i++)
- {
- if(!used[i])
- {
- if(dist[i]>dist[pos]+map[pos][i])
- {
- dist[i]=dist[pos]+map[pos][i];
- pas[i]=pas[pos]+pay[pos][i];
- }
- else if(dist[i]==dist[pos]+map[pos][i]&&pas[i]>pas[pos]+pay[pos][i])
- pas[i]=pas[pos]+pay[pos][i];
- }
- }
- }
- cout<<dist[q]<<" "<<pas[q]<<endl;
- }
- int main()
- {
- int a,b,c,d,m;
- while(cin>>n>>m&&n&&m)
- {
- for(i=0;i<=j;i++)
- for(j=0;j<=n;j++)
- {
- map[i][j]=MAX;
- pay[i][j]=MAX;
- }
- for(i=0;i<m;i++)
- {
- cin>>a>>b>>c>>d;
- if(map[a][b]>c)
- {
- map[a][b]=map[b][a]=c;
- pay[a][b]=pay[b][a]=d;
- }
- }
- cin>>p>>q;
- dijkstra();
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1411201410967.html
来源: http://www.codesnippet.cn/detail/1411201410967.html