題目連接：

　　http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=129723

題意：

　　給你一個(gè)n點(diǎn)m圖的邊

　　1到n有多條最短路，問你所有經(jīng)過的邊的總和*2是多少

題解：

　　對(duì)1,n分別求單源最短路徑上spfa

　　枚舉某條邊是否為最短上的邊

　　　即 邊權(quán)+disA[i] + disB[i] = 最短路長度，就是答案

#include<bits/stdc++.h> using namespace std; const int N = 1e6+20, M = 1e6+10, mod = 1e9+7, inf = 1e9+1000; typedef long long ll;int head[N],t,vis[N],dis[N],n,m,disA[N],disB[N]; struct edge{int to,value,next;}e[N*2];void add(int u,int v,int w) {e[t].next=head[u],e[t].to=v,e[t].value=w;head[u]=t++;}void init(){t = 0;memset(head,-1,sizeof(head)); }void spfa(int u) {for(int i=1;i<=n;i++) dis[i] = inf, vis[i] = 0;vis[1] = 1;dis[u] = 0;queue<int> q;q.push(u);while(!q.empty()) {int k = q.front();q.pop();vis[k] = 0;for(int i=head[k];i!=-1;i=e[i].next) {int to = e[i].to;if(dis[k] + e[i].value < dis[to]) {dis[to] = dis[k] + e[i].value;if(!vis[to]) {q.push(to);vis[to] = 1;}}}} } int main() {while(~scanf("%d%d",&n,&m)) {init();for(int i=1;i<=m;i++) {int a,b,c;scanf("%d%d%d",&a,&b,&c);a++,b++;add(a,b,c);add(b,a,c);}spfa(1);for(int i=1;i<=n;i++) disA[i] = dis[i];spfa(n);for(int i=1;i<=n;i++) disB[i] = dis[i];int mx = dis[1];ll ans = 0;for(int i=1;i<=n;i++) {for(int j=head[i];j!=-1;j=e[j].next) {int to = e[j].to;int value = e[j].value;if(disA[i] + disB[to] + value == mx) ans+=value;}}printf("%lld\n",2ll*ans);} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zxhl/p/5674847.html

總結(jié)

以上是生活随笔為你收集整理的UVALive 6885 Flowery Trails 最短路枚举的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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