{"id":115,"date":"2010-02-20T19:17:00","date_gmt":"2010-02-20T11:17:00","guid":{"rendered":"http:\/\/localhost\/?p=115"},"modified":"2010-02-20T19:17:00","modified_gmt":"2010-02-20T11:17:00","slug":"topcoder_srm_462_div_i_1000","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=115","title":{"rendered":"TopCoder SRM 462 Div I 1000"},"content":{"rendered":"

\u6bd4\u8d5b\u7684\u65f6\u5019\u6ca1\u6709A\u6389\u3002\u3002\u540e\u6765\u770b\u4e86ikki\u5927\u725b\u7684\u63d0\u793a\u7b97\u662f\u660e\u767d\u4e86\u3002\u3002
\u7531\u4e8en<=50\u60f3\u600e\u4e48\u5199\u90fd\u884c\u3002\u3002\u53ea\u8981\u522b\u66b4\u529b\u641c\u5c31\u53ef\u4ee5\u4e86\u56e7\u3002\u3002
\u9996\u5148\u679a\u4e3e\u6bcf\u6761\u8fb9\u3002\u7b97\u51fa\u5220\u6389\u8fd9\u6761\u8fb9\u540e\u4ece\u8fd9\u6761\u8fb9\u7684\u8d77\u70b9\u52302\u7684\u6700\u77ed\u8def\u3002\u3002
\u4e3a\u4e86\u65b9\u4fbf\u53ef\u4ee5\u628a\u6240\u6709\u8fb9\u7684\u90fd\u53cd\u8fc7\u6765\u3002\u3002\u8fd9\u6837\u5c31\u90fd\u53d8\u62102\u5230\u8fd9\u4e2a\u8d77\u70b9\u7684\u6700\u77ed\u8def\u4e86\u3002\u3002
\u7136\u540e\u7528spfa\u6765\u66f4\u65b0\u7b54\u6848\u3002\u3002\u5c31\u662f\u8bf4\u5b9a\u4e49dist[i]\u4ecei\u8282\u70b9\u8fd0\u7528\u6700\u4f18\u7b56\u7565\u52302\u7684\u8def\u7a0b\u3002\u3002
\u90a3\u4e48\u5173\u4e8ej\u8282\u70b9\u65b0\u7684\u4ee3\u4ef7\u5c31\u662f
\u5220:deletecost of edge(j,i) \/has been calculated before
\u4e0d\u5584:dist[i]+cost of edge(j,i)
\u90a3\u4e48\u65b0\u7684\u4ee3\u4ef7\u5c31\u662f\u8fd9\u4e24\u4e2a\u6700\u5927\u503c\u3002\u3002
\u7136\u540e\u7528\u8fd9\u4e2a\u6765\u66f4\u65b0j\u8282\u70b9\u3002\u3002\u8ddf\u5e73\u5e38\u7684spfa\u4e00\u6837\u5c31\u53ef\u4ee5\u4e86\u3002\u3002
\u6700\u540edist[0]\u5c31\u662f\u6240\u6c42\u4e86\u3002\u3002
Code\uff1a<\/p>\n

#include<\/strong> <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;<\/p>\n

class WarTransportation {
public:
int messenger(int, vector <string>);
};
const int maxn=100,inf=1<<29;int n;
struct edge
{
int s,t,c,dcost;bool e;
edge(int _s,int _t,int _c):s(_s),t(_t),c(_c),e(true){}
};
vector<edge> E[maxn];
typedef vector<edge>::iterator it;
void add_edge(vector<edge> E[maxn],int s,int t,int c)
{E[s].push_back(edge(s,t,c));}
void spfa(vector<edge> E[maxn],it d)
{
d->e=false;int dist[maxn];rep(i,n) dist[i]=inf;
bool inq[maxn]={0};inq[1]=true;dist[1]=0;
queue<int> Q;Q.push(1);
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];
for(it i=E[t].begin();i!=E[t].end();i++)if(i->e)
{
int ncost=cost+i->c;
if(ncost<dist[i->t])
{
dist[i->t]=ncost;
if(!inq[i->t]) Q.push(i->t),inq[i->t]=true;
}
}
}
d->dcost=dist[d->t];d->e=true;
}
int WarTransportation::messenger(int _n, vector <string> h) {
n=_n;
string A;for(int i=0;i<h.size();i++) A+=h[i];
istringstream in(A);int s,t,c;char tmp;
do
{
in>>s>>t>>c;s–;t–;
add_edge(E,t,s,c);
}while(in>>tmp);
rep(i,n)
{
for(it e=E[i].begin();e!=E[i].end();e++)
spfa(E,e),cout<<e->t+1<<"->"<<e->s+1<<":"<<e->dcost<<endl;
}
int dist[maxn];rep(i,n) dist[i]=inf;
bool inq[maxn]={0};inq[1]=true;dist[1]=0;
queue<int> Q;Q.push(1);
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];
for(it i=E[t].begin();i!=E[t].end();i++)
{
int ncost=max(cost+i->c,i->dcost);
if(ncost<dist[i->t])
{
dist[i->t]=ncost;
if(!inq[i->t]) Q.push(i->t),inq[i->t]=true;
}
}
}
if(dist[0]==inf) return -1;
return dist[0];
}<\/p>\n

<\/strong>\/\/Powered by [KawigiEdit] 2.0!<\/strong>
\u672c\u9ad8\u4eae\u4ee3\u7801\u4f7f\u7528codeHl\u751f\u6210\uff0c <\/p>\n","protected":false},"excerpt":{"rendered":"

\u6bd4\u8d5b\u7684\u65f6\u5019\u6ca1\u6709A\u6389\u3002\u3002\u540e\u6765\u770b\u4e86ikki\u5927\u725b\u7684\u63d0\u793a\u7b97\u662f\u660e\u767d\u4e86\u3002\u3002\u7531\u4e8en<=50\u60f3\u600e\u4e48\u5199\u90fd\u884c\u3002\u3002\u53ea\u8981\u522b\u66b4\u529b\u641c\u5c31\u53ef\u4ee5\u4e86\u56e7\u3002\u3002\u9996\u5148\u679a\u4e3e\u6bcf\u6761\u8fb9\u3002\u7b97\u51fa\u5220\u6389\u8fd9\u6761\u8fb9\u540e\u4ece\u8fd9\u6761\u8fb9\u7684\u8d77\u70b9\u52302\u7684\u6700\u77ed\u8def\u3002\u3002\u4e3a\u4e86\u65b9\u4fbf\u53ef\u4ee5\u628a\u6240\u6709\u8fb9\u7684\u90fd\u53cd\u8fc7\u6765\u3002\u3002\u8fd9\u6837\u5c31\u90fd\u53d8\u62102\u5230\u8fd9\u4e2a\u8d77\u70b9\u7684\u6700\u77ed\u8def\u4e86\u3002\u3002\u7136\u540e\u7528spfa\u6765\u66f4\u65b0\u7b54\u6848\u3002\u3002\u5c31\u662f\u8bf4\u5b9a\u4e49dist[i]\u4ecei\u8282\u70b9\u8fd0\u7528\u6700\u4f18\u7b56\u7565\u52302\u7684\u8def\u7a0b\u3002\u3002\u90a3\u4e48\u5173\u4e8ej\u8282\u70b9\u65b0\u7684\u4ee3\u4ef7\u5c31\u662f\u5220:deletecost of edge(j,i) \/has been calculated before\u4e0d\u5584:dist[i]+cost of edge(j,i)\u90a3\u4e48\u65b0\u7684\u4ee3\u4ef7\u5c31\u662f\u8fd9\u4e24\u4e2a\u6700\u5927\u503c\u3002\u3002\u7136\u540e\u7528\u8fd9\u4e2a\u6765\u66f4\u65b0j\u8282\u70b9\u3002\u3002\u8ddf\u5e73\u5e38\u7684spfa\u4e00\u6837\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u6700\u540edist[0]\u5c31\u662f\u6240\u6c42\u4e86\u3002\u3002Code\uff1a #include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <queue>#define rep(i,n) for(int i=0;i<n;i++)using namespace std; class WarTransportation {public: int messenger(int, vector <string>);};const int maxn=100,inf=1<<29;int n;struct edge{ int s,t,c,dcost;bool e; edge(int _s,int _t,int _c):s(_s),t(_t),c(_c),e(true){}};vector<edge> E[maxn];typedef vector<edge>::iterator it;void […]<\/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\/115"}],"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=115"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/115\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=115"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=115"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=115"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}