本文主要是介绍URAL - 1741 - Communication Fiend（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一个系统，目前是正版的，版本为1，现要下一些更新包来更新版本，更新包一定要接连的，若装了一个1——>3，那么下一次一定要装3——>xx的，Licensed的正版更新包只能装在正版系统上，不改变原系统的版权；Pirated的盗版更新包可以装在任何系统上，但装了后系统就变成盗版的了，而且再也回不到正版系统了；Cracked的正版更新包可以装在任何系统上，不改变原系统的版权。问能否从版本1更新到版本n，能的话输出"Online"及最小的下载量；否则输出"Offline"(2 ≤ n ≤ 10^4; 1 ≤ m ≤ 10^4, 1 ≤ xi < yi ≤ n; 1 ≤ di ≤ 10^6)。
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1741
——>>设d[i][0]为更新到版本i时为盗版系统的最小下载量，d[i][1]为更新到版本i时为正版系统的最小下载量，根据题意写状态转移方程就好。
注意数据范围，用64位整数，在这个问题上WA了一次
。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;const int maxn = 10000 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3f;int n, m, head[maxn], nxt[maxn], u[maxn], v[maxn], ecnt, f[maxn];
long long d[maxn][2], w[maxn];
bool vis[maxn];void init(){memset(head, -1, sizeof(head));ecnt = 0;
}void addEdge(int uu, int vv, long long ww, int ff){u[ecnt] = uu;v[ecnt] = vv;w[ecnt] = ww;f[ecnt] = ff;nxt[ecnt] = head[uu];head[uu] = ecnt;ecnt++;
}void dp(){memset(d, 0x3f3f, sizeof(d));memset(vis, 0, sizeof(vis));d[1][1] = 0;d[1][0] = INF;queue<int> qu;qu.push(1);while(!qu.empty()){int cur = qu.front(); qu.pop();vis[cur] = 0;for(int e = head[cur]; e != -1; e = nxt[e]){if(f[e] == 1) d[v[e]][1] = min(d[v[e]][1], d[cur][1] + w[e]);else if(f[e] == 2){d[v[e]][0] = min(d[v[e]][0], d[cur][0] + w[e]);d[v[e]][0] = min(d[v[e]][0], d[cur][1] + w[e]);}else{d[v[e]][1] = min(d[v[e]][1], d[cur][1] + w[e]);d[v[e]][0] = min(d[v[e]][0], d[cur][0] + w[e]);}if(!vis[v[e]]){qu.push(v[e]);vis[v[e]] = 1;}}}if(d[n][1] == INF && d[n][0] == INF) puts("Offline");else{puts("Online");printf("%I64d\n", min(d[n][1], d[n][0]));}
}int main()
{int x, y;long long dd;char s[10];while(scanf("%d%d", &n, &m) == 2){init();for(int i = 1; i <= m; i++){scanf("%d%d%I64d%s", &x, &y, &dd, s);if(s[0] == 'L') addEdge(x, y, dd, 1);else if(s[0] == 'P') addEdge(x, y, dd, 2);else addEdge(x, y, dd, 3);}dp();}return 0;
}
这篇关于URAL - 1741 - Communication Fiend（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
