- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- #define inf 10000000
- const int Maxn = 200005;
- int N,M;
- struct Edge{
- int v,next;
- int dt,ct;
- }edge[Maxn];
- int first[1005];
- int r,s,t;
- int vis[1005];
- struct BNode{
- int dist,cost;
- }P[1005];
- void addedge(int u, int v, int d, int p)
- {
- edge[r].next = first[u];
- edge[r].v = v;
- edge[r].dt = d;
- edge[r].ct = p;
- first[u] = r;
- r++;
- }
- int findminode()
- {
- int i,Maxn = inf;
- int index = 0;
- for(i = 1; i<=N; i++)
- if(P[i].dist<Maxn && !vis[i])
- {
- Maxn = P[i].dist;
- index = i;
- }
- if(index)
- {
- for(i = 1; i<=N; i++)
- if(P[i].cost<P[index].cost && !vis[i])index = i;
- }
- return index;
- }
- void solve()
- {
- int i;
- for(i = 1; i<=N; i++)
- P[i].dist = P[i].cost = inf;
- P[s].dist = P[s].cost = 0;
- memset(vis,0,sizeof(vis));
- int index = 1;
- while(index<N)
- {
- int x = findminode();
- if(!x)break;
- vis[x] = 1; index++;
- for(i = first[x]; i!=-1; i = edge[i].next)
- {
- int v = edge[i].v;
- if(P[x].dist+edge[i].dt<P[v].dist && !vis[v])
- {
- P[v].dist = P[x].dist+edge[i].dt;
- P[v].cost = P[x].cost+edge[i].ct;
- }
- else if(P[x].dist+edge[i].dt == P[v].dist && !vis[v])
- {
- if(P[x].cost+edge[i].ct<P[v].cost)P[v].cost = P[x].cost+edge[i].ct;
- }
- }
- }
- cout<<P[t].dist<<' '<<P[t].cost<<endl;
- }
- int main()
- {
- int i,u,v,d,p;
- while(scanf("%d%d",&N,&M)!=EOF)
- {
- if(N == 0 && M == 0)break;
- memset(first,-1,sizeof(first));
- r = 0;
- for(i = 0; i<M; i++)
- {
- scanf("%d%d%d%d",&u,&v,&d,&p);
- addedge(u,v,d,p);
- addedge(v,u,d,p);
- }
- scanf("%d%d",&s,&t);
- solve();
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1411201410974.html
来源: http://www.codesnippet.cn/detail/1411201410974.html