http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2249

題意：出若干個建筑之間的一些路，每條路都有對應(yīng)的長度和需要的花費(fèi)，問在保證源點(diǎn)1 到其他個點(diǎn)的距離最短的情況下，最少的花費(fèi)是多少

題解：最短路

C++版本一

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v,d,c; int ans,cnt,flag,temp,sum; int vis[N]; int cost[N]; struct node{int v,d,c;bool operator<(const node&S)const{if(d==S.d)return c>S.c;return d>S.d;} }s,x,tmp;priority_queue<node>q; vector<node>G[N]; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){while(~scanf("%d%d",&n,&m)&&n+m){while(!q.empty())q.pop();memset(vis,0,sizeof(vis));memset(cost,0,sizeof(cost));for(int i=1;i<=m;i++){scanf("%d%d%d%d",&u,&v,&d,&c);x.v=v;x.c=c;x.d=d;G[u].push_back(x);x.v=u;G[v].push_back(x);}x.v=1;x.d=0;x.c=0;q.push(x);while(!q.empty()){x=q.top();q.pop();if(vis[x.v])continue;vis[x.v]=1;//cout<<x.v<<" "<<x.c<<endl;cost[x.v]=x.c;for(int i=0,j=G[x.v].size();i<j;i++){tmp=G[x.v][i];if(vis[tmp.v]==0){tmp.d+=x.d;//tmp.c+=x.c;q.push(tmp);}}}ans=0;for(int i=1;i<=n;i++)ans+=cost[i],G[i].clear();cout<<ans<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

#include<iostream> #include<queue> #include<vector> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e4+5,INF=0x3f3f3f3f; int d[maxn]; int cost[maxn]; bool used[maxn]; int n,m; struct edge {int to,dis,c;edge(){}edge(int to,int dis,int c):to(to),dis(dis),c(c){} }; vector<edge> G[maxn]; void SPFA() {queue<int> que;memset(d,INF,sizeof(d));memset(used,false,sizeof(used));memset(cost,INF,sizeof(cost));d[1]=0;cost[1]=0;used[1]=true;que.push(1);while(que.size()){int u=que.front();que.pop();for(int i=0;i<G[u].size();i++){edge e=G[u][i];if(d[e.to]>d[u]+e.dis){d[e.to]=d[u]+e.dis;cost[e.to]=e.c;if(!used[e.to]){used[e.to]=true;que.push(e.to);}}else if(d[e.to]==d[u]+e.dis&&cost[e.to]>e.c)//可以更新到該點(diǎn)的最小花費(fèi){cost[e.to]=e.c;if(!used[e.to]){used[e.to]=true;que.push(e.to);}}}used[u]=false;}int ans=0;for(int i=1;i<=n;i++)ans+=cost[i];cout<<ans<<endl; } int main() {while(cin>>n>>m,n||m){for(int i=0;i<m;i++){int u,v,dis,c;cin>>u>>v>>dis>>c;G[u].push_back(edge(v,dis,c));G[v].push_back(edge(u,dis,c));}SPFA();for(int i=1;i<=n;i++)G[i].clear();}return 0; } 分類: 圖論--最短路

?

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的Road Construction的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。