今天看了刘哲大神的博客，真的写的很好啊；
题意：要首都（原点）和城市之间修路，有两个要求：1每个城市之间都有一组线连接他们（不用直接相连，这点很重要。）2每个城市和首都的最短路不能动；
这就决定了这道题是最短路而不是最小生成树，因为最小生成树达不到第二个条件，虽然他肯定是能达到第一个条件的 qrz；
并且第二个要求的情况就是松弛时 相等的情况；
方法1：可以用spfa，当相等的时候来得到最小的花费，然后把cost相加，
2：用优化过的dijkstra也可以，不过那个需要看一点优先队列的相关知识，我一会再写写再发一篇好了。
代码如下：#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn=20005; bool used[maxn]; long long d[maxn]; int n,m; int len; struct Tree{ int to; int from; int value; int next; int cost; }tree[maxn*2];//我开始忘记乘以2了，老是tle，re之类的，所以这个一定要注意， int head[maxn]; long long cost[maxn]; void add(int u,int v,int c,int d) { tree[len].from=u; tree[len].to=v; tree[len].value=c; tree[len].next=head[u]; tree[len].cost=d; head[u]=len++; } void init() { memset(head,-1,sizeof(head)); len=0; memset(cost,0x3f,sizeof(cost)); } int spfa() { queue<int>q; //int sum=0; memset(d,0x3f,sizeof(d)); memset(used,false,sizeof(used)); // d[0]=0;这个没用，因为肯定用不到0点。 cost[0]=0; while(!q.empty()) q.pop();//这个也没啥用， used[1]=true; q.push(1); d[1]=0; cost[1]=0; while(!q.empty()) { //ceshi=false; int u=q.front(); used[u]=false; q.pop(); for(int i=head[u];i!=-1;i=tree[i].next) { int s=tree[i].to; int w=tree[i].cost; if(d[s]>d[u]+tree[i].value) { if(!used[s]) {used[s]=true;//可以记录进出队列的次数判断是否存在负环； q.push(s); } d[s]=d[u]+tree[i].value; cost[s]=w; } else if(d[s]==d[u]+tree[i].value)//在最短路不变的情况下求最小的距离； { if(cost[s]>w) cost[s]=w; } } //q.pop(); } for(int i=1;i<=n;i++) cost[0]+=cost[i]; printf("%lld\n",cost[0]); return 0; } int main() { int a,b,c,d; while(~scanf("%d%d",&n,&m),m+n) { init(); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); add(a,b,c,d); add(b,a,c,d); } spfa(); //printf("%d\n",spfa()); } return 0; }
