Main » 2013 October 16 » [NOIP2012模拟赛No.21]第二短路
4:12 PM [NOIP2012模拟赛No.21]第二短路 |
O(Km)#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 200010 #define S 5010 #define L 400010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int last[N],pre[N],x[N],y[N],z[N],q[L],V[N]; int e[N],w[N],len,dis1[S],dis2[S],n,r; void add(int x,int y,int z) { pre[++len]=last[x]; last[x]=len; e[len]=y;w[len]=z; } void C(int &x){if (x==L) x=1;} void SPFA(int v0,int (&dis)[S]) { memset(dis,20,sizeof(dis)); dis[v0]=0;int h=0,t=1; memset(V,0,sizeof(V)); V[v0]=1;q[1]=v0; while (h<t) { h++;C(h); int u=q[h]; int p=last[u]; while (p) { int v=e[p],W=w[p]; if (dis[u]+W<dis[v]) { dis[v]=dis[u]+W; if (!V[v]) { t++;C(t); q[t]=v;V[v]=1; } } p=pre[p]; } V[u]=0; } } void init() { memset(last,0,sizeof(last));memset(pre,0,sizeof(pre)); memset(e,0,sizeof(e));memset(w,0,sizeof(w));len=0; } int main() { scanf("%d%d",&n,&r);init(); int i; FOR(i,1,r) { scanf("%d%d%d",&x[i],&y[i],&z[i]); add(x[i],y[i],z[i]);add(y[i],x[i],z[i]); } SPFA(n,dis1); SPFA(1,dis2); int m1=dis2[n],m2=2e9,t1,t2; FOR(i,1,r) { int d1=dis1[x[i]]+z[i]+dis2[y[i]]; int d2=dis1[y[i]]+z[i]+dis2[x[i]]; if (d1>m1&&d1<m2) m2=d1; if (d2>m1&&d2<m2) m2=d2; } printf("%d\n",m2); } |
|
|
| Total comments: 0 | |