\u8fd9\u9053\u9898\u7b97\u7ecf\u5178\u7684\u72b6\u538bDP\u4e86\u3002\u3002<\/p>\n
DP[S][P]\u8868\u793a\u5b8c\u6210\u4e86S\u96c6\u5408\u7684\u4efb\u52a1\uff0c\u73b0\u5728\u5728\u7b2cP\u4e2a\u4efb\u52a1\u7684\u843d\u811a\u70b9\u3002\u3002\u3002<\/p>\n
\u90a3\u4e48\u76f4\u63a5\u63a8\u5c31OK\u4e86\u3002\u3002<\/p>\n
\r\n#include<iostream>\r\n#include<string.h>\r\n#include<queue>\r\n#define REP(i,n) for(int i=0;i<n;i++)\r\n#define Renew(x,c) x=min(x,c)\r\n#define floyd(d) REP(k,n) REP(i,n) REP(j,n) Renew(d[i][j],d[i][k]+d[k][j]);\r\nusing namespace std;\r\nconst int maxn=120,inf=~0U>>3,maxb=13;\r\nint n,m,b,cnt=0;\r\nint dist[maxn][maxn];\r\nint Go[maxb+1],Reach[maxb+1];\r\n\r\nvoid init(){\r\n cin>>n>>m>>b;b--;cnt=0;\r\n REP(i,n) REP(j,n) dist[i][j]=(i==j?0:inf);\r\n while(m--) {\r\n int s,t,c;cin>>s>>t>>c;s--;t--;\r\n dist[s][t]=dist[t][s]=min(c,dist[s][t]);\r\n }\r\n int z;cin>>z; while(z--) {\r\n int s,t,c;cin>>s>>t>>c;s--;t--; while(c--) {\r\n Go[cnt]=s;Reach[cnt]=t;cnt++;\r\n }\r\n }\r\n Reach[cnt]=b;\r\n}\r\n\r\nint dp[1<<maxb][maxb+1];\r\n\r\nstruct node{\r\n int f,p;\r\n node(int f,int p):f(f),p(p){}\r\n};\r\n\r\nvoid solve(){\r\n floyd(dist); memset(dp,0,sizeof(dp));\r\n queue<node> Q; Q.push(node(0,cnt)); while(Q.size()){\r\n node cur=Q.front();Q.pop();\r\n int cost=dp[cur.f][cur.p];\r\n for(int i=0;i<cnt;i++)if(!(cur.f&(1<<i))) {\r\n int nf=cur.f|(1<<i); int get=cost+dist[Reach[cur.p]][Go[i]]+dist[Go[i]][Reach[i]];\r\n if(dp[nf][i]==0||dp[nf][i]>get) dp[nf][i]=get,Q.push(node(nf,i));\r\n }\r\n }\r\n int ans=inf; REP(i,cnt) Renew(ans,dp[(1<<cnt)-1][i]+dist[Reach[i]][b]); cout<<ans<<endl;\r\n}5\r\n\r\nint main(){\r\n int t;cin>>t; while(t--) {\r\n init(); solve();\r\n }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u8fd9\u9053\u9898\u7b97\u7ecf\u5178\u7684\u72b6\u538bDP\u4e86\u3002\u3002 DP[S][P]\u8868\u793a\u5b8c\u6210\u4e86S\u96c6\u5408\u7684\u4efb\u52a1\uff0c\u73b0\u5728\u5728\u7b2cP\u4e2a\u4efb\u52a1\u7684\u843d\u811a\u70b9\u3002\u3002\u3002 \u90a3\u4e48\u76f4\u63a5\u63a8\u5c31OK\u4e86\u3002\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/34"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=34"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/34\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=34"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=34"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=34"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}