[Usaco2009 Feb]Revamping Trails<\/p>\n
Time Limit:10000MS Memory Limit:65536K
Total Submit:43 Accepted:13
Case Time Limit:1000MS<\/p>\n
Description <\/strong><\/p>\n \u6bcf\u5929,\u519c\u592bJohn\u9700\u8981\u7ecf\u8fc7\u4e00\u4e9b\u9053\u8def\u53bb\u68c0\u67e5\u725b\u68daN\u91cc\u9762\u7684\u725b. \u519c\u573a\u4e0a\u6709M(1<=M<=50,000)\u6761\u53cc\u5411 \u4ed6\u60f3\u66f4\u65b0\u4e00\u4e9b\u8def\u7ecf\u6765\u51cf\u5c11\u6bcf\u5929\u82b1\u5728\u8def\u4e0a\u7684\u65f6\u95f4.\u5177\u4f53\u5730\u8bf4,\u4ed6\u60f3\u66f4\u65b0K (1 <= K <= 20)\u6761\u8def\u7ecf\uff0c Input <\/strong><\/p>\n * \u7b2c\u4e00\u884c: \u4e09\u4e2a\u7a7a\u683c\u5206\u5f00\u7684\u6570: N, M, \u548c K <\/p>\n * \u7b2c2..M+1\u884c: \u7b2ci+1\u884c\u6709\u4e09\u4e2a\u7a7a\u683c\u5206\u5f00\u7684\u6570\uff1aP1_i, P2_i, \u548c T_i <\/p>\n Output <\/strong><\/p>\n * \u7b2c\u4e00\u884c: \u66f4\u65b0\u6700\u591a\uff2b\u6761\u8def\u7ecf\u540e\u7684\u6700\u77ed\u8def\u7ecf\u957f\u5ea6\uff0e<\/p>\n Sample Input <\/strong><\/p>\n 4 4 1 Sample Output <\/strong><\/p>\n 1<\/p>\n Hint <\/strong><\/p>\n K\u662f1; \u66f4\u65b0\u9053\u8def3->4\u4f7f\u5f97\u4ece\uff13\u5230\uff14\u7684\u65f6\u95f4\u7531\uff11\uff10\uff10\u51cf\u5c11\u5230\uff10. \u6700\u65b0\u6700\u77ed\u8def\u7ecf\u662f1->3->4,\u603b\u7528\u65f6 Source <\/strong><\/p>\n Gold #include<cstdio> [Usaco2009 Feb]Revamping Trails Time Limit:10000MS Memory Limit:65536KTotal Submit:43 Accepted:13 Case Time Limit:1000MS Description \u6bcf\u5929,\u519c\u592bJohn\u9700\u8981\u7ecf\u8fc7\u4e00\u4e9b\u9053\u8def\u53bb\u68c0\u67e5\u725b\u68daN\u91cc\u9762\u7684\u725b. \u519c\u573a\u4e0a\u6709M(1<=M<=50,000)\u6761\u53cc\u5411 \u6ce5\u571f\u9053\u8def,\u7f16\u53f7\u4e3a1..M. \u9053\u8defi\u8fde\u63a5\u725b\u68daP1_i\u548cP2_i (1 <= P1_i <= N; 1 <= P2_i<= N). John\u9700\u8981T_i (1 <= T_i <= 1,000,000)\u65f6\u95f4\u5355\u4f4d\u7528\u9053\u8defi\u4eceP1_i\u8d70\u5230P2_i\u6216\u8005\u4eceP2_i \u8d70\u5230P\uff11_i \u4ed6\u60f3\u66f4\u65b0\u4e00\u4e9b\u8def\u7ecf\u6765\u51cf\u5c11\u6bcf\u5929\u82b1\u5728\u8def\u4e0a\u7684\u65f6\u95f4.\u5177\u4f53\u5730\u8bf4,\u4ed6\u60f3\u66f4\u65b0K (1 <= K <= 20)\u6761\u8def\u7ecf\uff0c \u5c06\u5b83\u4eec\u6240\u987b\u65f6\u95f4\u51cf\u4e3a\uff10\uff0e\u5e2e\u52a9FJ\u9009\u62e9\u54ea\u4e9b\u8def\u7ecf\u9700\u8981\u66f4\u65b0\u4f7f\u5f97\u4ece\uff11\u5230N\u7684\u65f6\u95f4\u5c3d\u91cf\u5c11. Input * \u7b2c\u4e00\u884c: \u4e09\u4e2a\u7a7a\u683c\u5206\u5f00\u7684\u6570: N, M, \u548c K * \u7b2c2..M+1\u884c: \u7b2ci+1\u884c\u6709\u4e09\u4e2a\u7a7a\u683c\u5206\u5f00\u7684\u6570\uff1aP1_i, P2_i, \u548c T_i Output […]<\/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\/214"}],"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=214"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/214\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u6ce5\u571f\u9053\u8def,\u7f16\u53f7\u4e3a1..M. \u9053\u8defi\u8fde\u63a5\u725b\u68daP1_i\u548cP2_i (1 <= P1_i <= N; 1 <= P2_i<= N).
John\u9700\u8981T_i (1 <= T_i <= 1,000,000)\u65f6\u95f4\u5355\u4f4d\u7528\u9053\u8defi\u4eceP1_i\u8d70\u5230P2_i\u6216\u8005\u4eceP2_i
\u8d70\u5230P\uff11_i <\/p>\n
\u5c06\u5b83\u4eec\u6240\u987b\u65f6\u95f4\u51cf\u4e3a\uff10\uff0e\u5e2e\u52a9FJ\u9009\u62e9\u54ea\u4e9b\u8def\u7ecf\u9700\u8981\u66f4\u65b0\u4f7f\u5f97\u4ece\uff11\u5230N\u7684\u65f6\u95f4\u5c3d\u91cf\u5c11. <\/p>\n
1 2 10
2 4 10
1 3 1
3 4 100<\/p>\n
\u4e3a\uff11\u5355\u4f4d.
N<=10000<\/p>\n
\u8fd9\u4e2a\u5f88\u660e\u663e\u662f\u5206\u5c42\u56fe\u7684\u6700\u77ed\u8def\uff0c\u4e0d\u8fc7\u6211\u7684\u505a\u6cd5\u6709\u70b9\u8be1\u5f02\u3002\u5c31\u662f\u5bf9\u6bcf\u4e00\u5c42\u7528dijstra\u7b97\u51fa\u6700\u77ed\u8def\u4e4b\u540e\u518d\u66f4\u65b0\u4e0b\u4e00\u5c42\u3002\u90a3\u6837\u7a7a\u95f4\u6d88\u8017\u5f88\u4f4e\u800c\u4e14\u901f\u5ea6\u6bd4\u6807\u7a0b\u5feb\u4e00\u500d\u6655\u3002\u3002
Code\uff1a<\/p>\n
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int maxn=10000+10;
typedef long long ll;
const ll inf=ll(1)<<60;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void InsEdge(int s,int t,int c){E[s].pb(Edge(t,c));E[t].pb(Edge(s,c));}
int n,m,k;
ll Dp[2][maxn];
struct State
{
int p;ll c;
State(int _p,ll _c):p(_p),c(_c){}
bool operator<(const State&o)const
{return c>o.c;}
};
priority_queue<State> Q;
int main()
{
cin>>n>>m>>k;int s,t,c;
rep(i,m)scanf("%d %d %d",&s,&t,&c),InsEdge(s-1,t-1,c);
int now=0,next=1;rep(i,n)Dp[next][i]=inf;Dp[next][0]=0;
rep(o,k+1)
{
swap(now,next);
rep(i,n)if(Dp[now][i]!=inf) Q.push(State(i,Dp[now][i]));
\/\/Update now
while(Q.size())
{
State t=Q.top();Q.pop();if(Dp[now][t.p]!=t.c)continue;
Dp[now][t.p]=t.c;int ncost;
for(eit e=E[t.p].begin();e!=E[t.p].end();++e)
if((ncost=t.c+e->c)<Dp[now][e->t])
Dp[now][e->t]=ncost,Q.push(State(e->t,ncost));
}
\/\/Update next
rep(i,n) Dp[next][i]=Dp[now][i];
rep(i,n) for(eit e=E[i].begin();e!=E[i].end();e++)
Dp[next][e->t]<?=Dp[now][i];
}
cout<<Dp[now][n-1]<<endl;
}<\/p>\n","protected":false},"excerpt":{"rendered":"