Aizu2249-Road Construction-（Dijkstra）
https://vjudge.net/problem/Aizu-2249
题意：计划图中有n个城市m条路，首都是1号城市，要选一些路去修，让各个城市到首都的路径最短，在路径最短的情况下修路费用最小。
题解：首都1号→源点→单源最短路→Dijkstra。对Dijkstra稍作修改，如果路径同样小，取费用更小的。费用是把这个点加进连通图的费用，而不是修出这条路的费用，否则最后累加会和之前相同路段的费用重复。（一道破题搞了我一个下午，条件没弄清楚，就是差一点，请大佬帮看一下，30秒修改后AC。）
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; int n,m; struct edge { int to; int dis; int cost; }; int d[10086]; int c[10086]; vector<edge>e[10086]; bool vis[10086]; int money; void Dijkstra() { memset(vis,false,sizeof(vis)); memset(d,inf,sizeof(d)); memset(c,inf,sizeof(c)); d[1]=0; c[1]=0; money=0;///总花费 while(true) { int v=-1; for(int u=1;u<=n;u++) { if( !vis[u] && ( v==-1 || d[u]<d[v] ) ) v=u; } if(v==-1) break; vis[v]=true; money+=c[v];///对于已经确定的点 修路的费用 累加起来 for(int i=0;i<e[v].size();i++) { int u=e[v][i].to; int dis=e[v][i].dis; int cost=e[v][i].cost; if( d[u] > d[v]+dis || ( d[u]==d[v]+dis && cost<c[u] ) )///核心判断 { d[u] = d[v]+dis; c[u] = cost;///c[u]是指 把u加进图的费用，而不是在v的费用基础上加的 } } } } int main() { while(scanf("%d%d",&n,&m)&&(n+m)) { for(int i=1;i<=n;i++) e[i].clear(); for(int i=1;i<=m;i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); e[a].push_back({ b,c,d } ); e[b].push_back({ a,c,d } ); } Dijkstra(); int ans=0; for(int i=1;i<=n;i++) ans+=c[i]; printf("%d ",money); } return 0; }