算是学了图dp后的第一次应用吧。题目其实真的是非常不严谨，什么都没说，基本靠猜，而且严格来说数据应该会有爆int的，不过不管那么多啦，思路对了就好－ －0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129 |
#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<queue>#define ll long long#define maxn 5000#define maxm 1000000#define inf 0x3f3f3f3fusing
namespace std;vector<int> G[maxn+50];struct
Node{ int
v,k; Node(){} Node(int
vi,int
ki):v(vi),k(ki){}};int
m,n,k;int
dis[maxn+50][55];int
num[maxn+50][55];int
vis[maxn+50][55];int
vtype[maxn];int
main(){ while(cin>>m>>n>>k) { for(int
i=0;i<=n;i++) G[i].clear(); int
xi,yi; for(int
i=0;i<n;i++) { scanf("%d%d",&xi,&yi); vtype[xi]=yi; } for(int
i=0;i<m;i++){ scanf("%d%d",&xi,&yi); G[xi].push_back(yi); G[yi].push_back(xi); } memset(dis,0x3f,sizeof(dis)); memset(num,0,sizeof(num)); queue<Node> que; if(vtype[1]==0){ dis[1][0]=0; num[1][0]=1; que.push(Node(1,0)); } else{ dis[1][1]=0; num[1][1]=1; que.push(Node(1,1)); } while(!que.empty()){ Node xx=que.front();que.pop(); vis[xx.v][xx.k]=0; int
u=xx.v; int
kk=xx.k; for(int
i=0;i<G[u].size();i++){ int
v=G[u][i]; if(vtype[v]==0){ if(vis[v][kk]){ if(dis[u][kk]+1<dis[v][kk]){ dis[v][kk]=dis[u][kk]+1; num[v][kk]=num[u][kk]; } else
if(dis[u][kk]+1==dis[v][kk]){ num[v][kk]+=num[u][kk]; } } else{ if(dis[u][kk]+1<dis[v][kk]){ dis[v][kk]=dis[u][kk]+1; num[v][kk]=num[u][kk]; que.push(Node(v,kk)); vis[v][kk]=1; } else
if(dis[u][kk]+1==dis[v][kk]){ num[v][kk]+=num[u][kk]; que.push(Node(v,kk)); vis[v][kk]=1; } } } else{ if(kk==k) continue; if(vis[v][kk+1]){ if(dis[u][kk]+1<dis[v][kk+1]){ dis[v][kk+1]=dis[u][kk]+1; num[v][kk+1]=num[u][kk]; } else
if(dis[u][kk]+1==dis[v][kk+1]){ num[v][kk+1]+=num[u][kk]; } } else{ if(dis[u][kk]+1<dis[v][kk+1]){ dis[v][kk+1]=dis[u][kk]+1; num[v][kk+1]=num[u][kk]; que.push(Node(v,kk+1)); vis[v][kk+1]=1; } else
if(dis[u][kk]+1==dis[v][kk+1]){ num[v][kk+1]+=num[u][kk]; que.push(Node(v,kk+1)); vis[v][kk+1]=1; } } } } } int
mdis=inf; for(int
i=0;i<=k;i++){ mdis=min(mdis,dis[n][i]); } if(mdis==inf) { puts("Impossible!");continue; } int
ans=0; for(int
i=0;i<=k;i++){ if(dis[n][i]==mdis) ans+=num[n][i]; } cout<<ans<<endl; } return
0;} |
ZOJ2923 Calculate Roads(SPFA上的dp),布布扣,bubuko.com
ZOJ2923 Calculate Roads(SPFA上的dp)
原文：http://www.cnblogs.com/chanme/p/3628995.html