首页 > 代码库 > HDU 4360 As long as Binbin loves Sangsang spfa
HDU 4360 As long as Binbin loves Sangsang spfa
题意:
给定n个点m条边的无向图
每次必须沿着LOVE走,到终点时必须是完整的LOVE,且至少走出一个LOVE,
问这样情况下最短路是多少,在一样短情况下最多的LOVE个数是多少。
有自环。
#include <cstdio> #include <cstring> #include <cmath> #include <queue> #include <iostream> #include <algorithm> using namespace std; typedef __int64 ll; const ll Inf = 4611686018427387904LL; const int N = 1314 + 100; const int E = 13520 * 2 + 100; const int M = N * 4 + 100; struct Edge { ll len; int v, f, nex; Edge() { } Edge(int _v, int _f, ll _len, int _nex) { v = _v; f = _f; len = _len; nex = _nex; } }; struct node{ int to, f; node(int b=0,int d=0):to(b),f(d){} }; Edge eg[E]; ll dis[N][4], tim[N][4]; bool vis[N][4]; int T, n, g[N], idx; int re(char c) { if (c == 'L') return 0; else if (c == 'O') return 1; else if (c == 'V') return 2; else return 3; } void addedge(int u, int v, ll len, int f) { eg[idx] = Edge(v, f, len, g[u]); g[u] = idx++; } void spfa() { memset(vis, 0, sizeof vis); for (int i = 0; i < n; ++i) for (int j = 0; j < 4; ++j) { dis[i][j] = Inf; tim[i][j] = 0; } queue<node>q; q.push(node(0,3)); dis[0][3] = 0; tim[0][3] = 0; while(!q.empty()){ node u = q.front(); q.pop(); vis[u.to][u.f] = 0; for(int i = g[u.to]; ~i; i = eg[i].nex){ int y = eg[i].v, f = eg[i].f; if(f != (u.f+1)%4)continue; bool yes = false; if(dis[y][f] > dis[u.to][u.f]+eg[i].len) { dis[y][f] = dis[u.to][u.f]+eg[i].len; tim[y][f] = tim[u.to][u.f]; if(f == 3) tim[y][f]++; yes = true; } else if(dis[y][f] == dis[u.to][u.f]+eg[i].len) { ll tmp = tim[u.to][u.f]; if(f == 3) tmp++; if(tmp > tim[y][f]) tim[y][f] = tmp, yes = true; } else if(tim[y][f]==0) { ll tmp = tim[u.to][u.f]; if(f == 3) tmp++; if(tmp > tim[y][f]) dis[y][f] = dis[u.to][u.f]+eg[i].len, tim[y][f] = tmp, yes = true; } if(yes && vis[y][f] == 0) vis[y][f] = 1, q.push(node(y, f)); } } } void work() { int m, u, v; ll len; char s[5]; memset(g, -1, sizeof g); idx = 0; scanf("%d %d", &n, &m); while (m -- > 0) { scanf("%d%d%I64d%s", &u, &v, &len, s); -- u; -- v; addedge(u, v, len, re(s[0])); addedge(v, u, len, re(s[0])); } spfa(); ll ansdis = dis[n - 1][3], ansnum = tim[n - 1][3]; printf("Case %d: ", ++T); if (ansdis == Inf || ansnum == 0) { puts("Binbin you disappoint Sangsang again, damn it!"); } else { printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %I64d LOVE strings at last.\n", ansdis, ansnum); } } int main() { int cas; T = 0; scanf("%d", &cas); while (cas -- > 0) work(); return 0; } /* 99 4 4 1 2 1 L 2 4 1 O 4 1 1 V 1 4 1 E 1 4 1 1 1 L 1 1 1 O 1 1 1 V 1 1 1 E 1 0 */
HDU 4360 As long as Binbin loves Sangsang spfa
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。