DP/最短路 URAL 1741 Communication Fiend

 1 /*
 2     题意：程序从1到n版本升级，正版+正版->正版，正版+盗版->盗版，盗版+盗版->盗版
 3             正版+破解版->正版，盗版+破解版->盗版
 4     DP：每种情况考虑一遍，递推就行了
 5     注意：开long long
 6 */
 7 #include <cstdio>
 8 #include <iostream>
 9 #include <algorithm>
10 #include <cstring>
11 #include <cmath>
12 using namespace std;
13 
14 const int MAXN = 1e4 + 10;
15 const int INF = 0x3f3f3f3f;
16 struct Node
17 {
18     int u, v, w;
19     char s[10];
20 }node[MAXN];
21 long long dp[MAXN][2];
22 
23 bool cmp(Node x, Node y)
24 {
25     if (x.u == y.u)    return     x.v < y.v;
26     return x.u < y.u;
27 }
28 
29 int main(void)        //URAL 1741 Communication Fiend
30 {
31     //freopen ("T.in", "r", stdin);
32 
33     int n, m;
34     while (scanf ("%d%d", &n, &m) == 2)
35     {
36         for (int i=1; i<=m; ++i)
37         {
38             scanf ("%d %d %d %s", &node[i].u, &node[i].v, &node[i].w, &node[i].s);
39         }
40         sort (node+1, node+1+m, cmp);
41 
42         memset (dp, -1, sizeof (dp));
43         dp[1][0] = 0;
44         for (int i=1; i<=m; ++i)
45         {
46             Node a = node[i];
47             if (a.s[0] == 'L')
48             {
49                 if (dp[a.u][0] != -1 && (dp[a.v][0] == -1 || dp[a.v][0] > dp[a.u][0] + a.w))
50                 {
51                     dp[a.v][0] = dp[a.u][0] + a.w;
52                 }
53             }
54             else if (a.s[0] == 'P')
55             {
56                 if (dp[a.u][0] != -1 && (dp[a.v][1] == -1 || dp[a.v][1] > dp[a.u][0] + a.w))
57                 {
58                     dp[a.v][1] = dp[a.u][0] + a.w;
59                 }
60                 if (dp[a.u][1] != -1 && (dp[a.v][1] == -1 || dp[a.v][1] > dp[a.u][1] + a.w))
61                 {
62                     dp[a.v][1] = dp[a.u][1] + a.w;
63                 }
64             }
65             else if (a.s[0] == 'C')
66             {
67                 if (dp[a.u][0] != -1 && (dp[a.v][0] == -1 || dp[a.v][0] > dp[a.u][0] + a.w))
68                 {
69                     dp[a.v][0] = dp[a.u][0] + a.w;
70                 }
71                 if (dp[a.u][1] != -1 && (dp[a.v][1] == -1 || dp[a.v][1] > dp[a.u][1] + a.w))
72                 {
73                     dp[a.v][1] = dp[a.u][1] + a.w;
74                 }
75             }
76         }
77 
78         if (dp[n][0] == -1 && dp[n][1] == -1)    puts ("Offline");
79         else
80         {
81             puts ("Online");
82             if (dp[n][0] == -1)    printf ("%I64d
", dp[n][1]);
83             else if (dp[n][1] == -1)    printf ("%I64d
", dp[n][0]);
84             else    printf ("%I64d
", min (dp[n][0], dp[n][1]));
85         }
86     }
87 
88     return 0;
89 }
90 
91 /*
92 Online
93 Offline
94 */

  1 /*
  2     WA了4，5发，第一是抄Kuangbin的模板抄错了；第二是选取的INF值太小了
  3     以后学习一下最值的选取的方法:)
  4 */
  5 #include <cstdio>
  6 #include <iostream>
  7 #include <algorithm>
  8 #include <cstring>
  9 #include <vector>
 10 #include <cmath>
 11 #include <queue>
 12 using namespace std;
 13 
 14 const int MAXN = 1e4 + 10;
 15 const int INF = 0x3f3f3f3f;
 16 const int INFF = 0x7fffffff;
 17 const long long inf = ((long long)1<<50);
 18 struct Edge
 19 {
 20     int v, w;
 21     int f;
 22     Edge (int _v = 0, int _w = 0, int _f = 0) : v (_v), w (_w), f (_f) {}
 23 };
 24 bool vis[MAXN];
 25 int cnt[MAXN];
 26 long long d[MAXN][2];
 27 vector<Edge> G[MAXN];
 28 int n, m;
 29 
 30 void add_edge(int u, int v, int w, int f)
 31 {
 32     G[u].push_back (Edge (v, w, f));
 33 }
 34 
 35 bool SPFA(int s)
 36 {
 37     memset (cnt, 0, sizeof (cnt));
 38     memset (vis, false, sizeof (vis));
 39     for (int i=1; i<=n; ++i)    d[i][0] = d[i][1] = inf;
 40     vis[s] = true;    d[s][0] = 0;    cnt[s] = 1;
 41 
 42     queue<int> Q;    Q.push (s);
 43     while (!Q.empty ())
 44     {
 45         int u = Q.front ();    Q.pop ();
 46         vis[u] = false;                        //失误！
 47         for (int i=0; i<G[u].size (); ++i)
 48         {
 49             int v = G[u][i].v;    int w = G[u][i].w;    int f = G[u][i].f;
 50             if (f == 0)
 51             {
 52                 if (d[v][0] > d[u][0] + w)    d[v][0] = d[u][0] + w;
 53             }
 54             else if (f == 1)
 55             {
 56                 if (d[v][1] > d[u][0] + w)    d[v][1] = d[u][0] + w;
 57                 if (d[v][1] > d[u][1] + w)    d[v][1] = d[u][1] + w;
 58             }
 59             else
 60             {
 61                 if (d[v][0] > d[u][0] + w)    d[v][0] = d[u][0] + w;
 62                 if (d[v][1] > d[u][1] + w)    d[v][1] = d[u][1] + w;
 63             }
 64             if (!vis[v])
 65             {
 66                 vis[v] = true;    Q.push (v);
 67                 if (++cnt[v] > n)    return true;
 68             }
 69         }
 70     }
 71 
 72     return false;
 73 }
 74 
 75 int main(void)        //URAL 1741 Communication Fiend
 76 {
 77     //freopen ("T.in", "r", stdin);
 78 
 79     while (scanf ("%d%d", &n, &m) == 2)
 80     {
 81         for (int i=1; i<=n; ++i)    G[i].clear ();
 82         for (int i=1; i<=m; ++i)
 83         {
 84             int u, v, w, f;    char s[10];
 85             scanf ("%d %d %d %s", &u, &v, &w, &s);
 86             if (s[0] == 'L')    f = 0;
 87             else if (s[0] == 'P')    f = 1;
 88             else if (s[0] == 'C')    f = -1;
 89             add_edge (u, v, w, f);
 90         }
 91 
 92         if (!SPFA (1))
 93         {
 94             long long ans = min (d[n][0], d[n][1]);
 95             if (ans == inf)    puts ("Offline");
 96             else    {puts ("Online");    printf ("%I64d
", ans);}
 97         }
 98     }
 99 
100     return 0;
101 }
102 
103 /*
104 Online
105 Offline
106 */

SPFA

编译人生，运行世界！