刷个简单的DP缓缓心情
1A
1 #include <iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<stdlib.h>
6 #include<vector>
7 using namespace std;
8 #define N 10010
9 vector<int>q[N];
10 #define LL __int64
11 #define INF 1e10
12 LL dp[N][4];
13 int o[N];
14 struct node
15 {
16 int x,y,d;
17 char s[10];
18 }p[N];
19 int main()
20 {
21 int i,j,n,m;
22 scanf("%d%d",&n,&m);
23 for(i = 1; i <= m ; i++)
24 {
25 scanf("%d%d%d%s",&p[i].x,&p[i].y,&p[i].d,p[i].s);
26 q[p[i].y].push_back(i);
27 }
28 dp[i][1] = 0;
29 dp[i][2] = INF;
30 dp[i][3] = INF;
31 for(i = 2; i <= n ; i++)
32 {
33 dp[i][1] = dp[i][2] = dp[i][3] = INF;
34 for(j = 0 ; j < (int)q[i].size() ; j++)
35 {
36 int v = q[i][j],k,x = p[v].x,w = p[v].d;
37 if(strcmp(p[v].s,"Licensed")==0)
38 k = 1;
39 else if(strcmp(p[v].s,"Cracked")==0)
40 k = 2;
41 else k = 3;
42 if(k==1)
43 {
44 dp[i][1] = min(dp[i][1],min(dp[x][1]+w,dp[x][2]+w));
45 }
46 else if(k==2)
47 {
48 dp[i][2] = min(dp[i][2],min(dp[x][2]+w,dp[x][1]+w));
49 dp[i][3] = min(dp[i][3],dp[x][3]+w);
50 }
51 else
52 {
53 dp[i][3] = min(dp[i][3],dp[x][3]+w);
54 dp[i][3] = min(dp[i][3],dp[x][2]+w);
55 dp[i][3] = min(dp[i][3],dp[x][1]+w);
56 }
57 }
58 }
59 LL ans = INF;
60 for(i = 1; i <= 3 ; i++)
61 ans = min(ans,dp[n][i]);
62 if(ans==INF)
63 puts("Offline");
64 else
65 {
66 puts("Online");
67 printf("%I64d\n",ans);
68 }
69 return 0;
70 }
View Code
转载于:https://www.cnblogs.com/shangyu/p/3379198.html