首页 > 代码库 > Invitation Cards---poj1511（spfa）
Invitation Cards---poj1511（spfa）
题目链接：http://poj.org/problem?id=1511
有向图有n个点m条边，求点1到其他n-1个点的最短距离和+其他点到点1的最小距离和；
和poj3268一样，但是本题的数据范围较大，只能用spfa+邻接表写，不能用vector；
两个spfa即可；
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <queue>#include <algorithm>#include <map>#include <string>typedef long long LL;///#define INF 0x3f3f3f3f#define INF 100000000000000#define N 1000100using namespace std;struct node{ int v; LL w; node(){}; node(int v, LL w):v(v),w(w){}};vector<node > G[N];vector<node > G1[N];int vis[N], n, m;LL dist[N];LL spfa1(int s){ for(int i=1; i<=n; i++) dist[i] = INF; dist[s] = 0; queue<int> Q; Q.push(s); memset(vis, 0, sizeof(vis)); vis[s] = 1; while(!Q.empty()) { int p = Q.front(); Q.pop(); vis[p] = 0; for(int i=0, len=G[p].size(); i<len; i++) { node q = G[p][i]; if(dist[q.v] > dist[p] + q.w) { dist[q.v] = dist[p] + q.w; if(!vis[q.v]) { vis[q.v] = 1; Q.push(q.v); } } } } LL ans = 0; for(int i=1; i<=n; i++) ans += dist[i]; return ans;}LL spfa2(int s){ queue<int>Q; for(int i=1; i<=n; i++) dist[i] = INF; memset(vis, 0, sizeof(vis)); vis[s] = 1; dist[s] = 0; Q.push(s); while(!Q.empty()) { int p = Q.front(); Q.pop(); vis[p] = 0; for(int i=0, len=G1[p].size(); i<len; i++) { node q = G1[p][i]; if(dist[q.v] > dist[p] + q.w) { dist[q.v] = dist[p] + q.w; if(!vis[q.v]) { vis[q.v] = 1; Q.push(q.v); } } } } LL ans = 0; for(int i=1; i<=n; i++) ans += dist[i]; return ans;}int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &m); for(int i=1; i<=n; i++) { G[i].clear(); G1[i].clear(); } for(int i=1; i<=m; i++) { int u, v; LL w; scanf("%d %d %I64d", &u, &v, &w); G[u].push_back(node(v, w)); G1[v].push_back(node(u, w)); } LL ans = spfa1(1); ans += spfa2(1); printf("%I64d\n", ans); } return 0;}
Invitation Cards---poj1511（spfa）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。