题意:求无向图从起点到终点最多停留k次的最短路
设d[i][j]表示走了i步后到达点j的最小代价,看似最短路,实则dp,因为求解过程中i是递增的,不存在环,直接递推求解即可
什么?你说最短路也属于dp?那没事了
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=100+10,inf=0x3f3f3f3f; 5 int n,m,hd[N],d[N][N],ne,ka,Q; 6 char s1[30],s2[30]; 7 struct E {int v,c,nxt;} e[20010]; 8 void link(int u,int v,int c) {e[ne]= {v,c,hd[u]},hd[u]=ne++;} 9 map<string,int> s2id; 10 int id(string s) { 11 if(s2id.count(s))return s2id[s]; 12 int n=s2id.size()+1; 13 return s2id[s]=n; 14 } 15 void solve() { 16 for(int i=0; i<=n; ++i)for(int j=1; j<=n; ++j)d[i][j]=inf; 17 d[0][id("Calgary")]=0; 18 for(int t=0; t<n; ++t) 19 for(int u=1; u<=n; ++u)if(d[t][u]<inf) 20 for(int i=hd[u]; ~i; i=e[i].nxt) { 21 int v=e[i].v,c=e[i].c; 22 d[t+1][v]=min(d[t+1][v],d[t][u]+c); 23 } 24 } 25 int qry(int k) { 26 int ret=inf; 27 for(int t=0; t<=k; ++t)ret=min(ret,d[t][id("Fredericton")]); 28 return ret; 29 } 30 31 int main() { 32 int _; 33 for(scanf("%d",&_); _--;) { 34 if(ka++)puts(""); 35 printf("Scenario #%d\n",ka); 36 s2id.clear(); 37 memset(hd,-1,sizeof hd),ne=0; 38 scanf("%d",&n); 39 for(int i=1; i<=n; ++i)scanf("%*s"); 40 scanf("%d",&m); 41 while(m--) { 42 int c; 43 scanf("%s%s%d",s1,s2,&c); 44 link(id(s1),id(s2),c); 45 } 46 solve(); 47 for(scanf("%d",&Q); Q--;) { 48 int k; 49 scanf("%d",&k); 50 k++; 51 k=min(k,n); 52 int ans=qry(k); 53 if(ans==inf)puts("No satisfactory flights"); 54 else printf("Total cost of flight(s) is $%d\n",ans); 55 } 56 } 57 return 0; 58 }