题目链接：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2249
思路：最短路径下处理花费最小.
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#define MAXSIZE 1000005
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
//给出若干个建筑之间的一些路，每条路都有对应的长度和需要的花费，
//问在保证源点1 到其他个点的距离最短的情况下，最少的花费是多少
int n,m,vis[MAXSIZE],a[MAXSIZE],k,dist[MAXSIZE],id[MAXSIZE];
struct node{int u;int v;int w;int c;int next;
}G[MAXSIZE];
void Add(int u,int v,int w,int c){G[k].u = u;G[k].v = v;G[k].w = w;G[k].c = c;G[k].next = a[u];a[u] = k++;
}
int dij(){memset(vis,0,sizeof(vis));memset(id,-1,sizeof(id));dist[1] = 0;int minn ,p;for(int i=1;i<k;i++){minn = INF;for(int j=1;j<=n;j++){if(!vis[j] && dist[j] < minn){minn = dist[j];p = j;}}if(minn == INF)break;vis[p] = 1;for(int j=a[p];j!=-1;j=G[j].next){int v = G[j].v;if(dist[v] > dist[p] + G[j].w && !vis[v]) //距离更短就更新{dist[v] = dist[p] + G[j].w;id[v] = j;}//距离相同，花费更小就更新else if(id[v]!=-1 && dist[v] == dist[p] + G[j].w && G[j].c < G[id[v]].c && !vis[v]){id[v] = j;}}}int sum=0;for(int i=1;i<=n;i++){if(id[i] == -1)continue;elsesum += G[id[i]].c;}return sum;
}
void Init(){memset(a,-1,sizeof(a));memset(vis,0,sizeof(vis));for(int i=0;i<MAXSIZE;i++)dist[i] = INF;k = 1;
}
int main(){int u,v,w,c;while(scanf("%d%d",&n,&m),n+m){Init();for(int i=1;i<=m;i++){scanf("%d%d%d%d",&u,&v,&w,&c);Add(u,v,w,c);Add(v,u,w,c);}int ans = dij();printf("%d\n",ans);}return 0;
}
/*3 3
1 2 1 2
2 3 2 1
3 1 3 2
5 5
1 2 2 2
2 3 1 1
1 4 1 1
4 5 1 1
5 3 1 1
5 10
1 2 32 10
1 3 43 43
1 4 12 52
1 5 84 23
2 3 58 42
2 4 86 99
2 5 57 83
3 4 11 32
3 5 75 21
4 5 23 43
5 10
1 2 1 53
1 3 1 65
1 4 1 24
1 5 1 76
2 3 1 19
2 4 1 46
2 5 1 25
3 4 1 13
3 5 1 65
4 5 1 34
0 0
Output for the Sample Input
3
5
137
218*/