BZOJ4283: 魔法少女伊莉雅（最短路径图+最短路径树）

题面

传送门

题解

太长了不想写了→_→

题解

//minamoto
#include
#define R register
#define inf 0x3f3f3f3f
#define pb push_back
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;iI;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
templateinline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;while(z[++Z]=x%10+48,x/=10);while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=5e5+5,M=1e6+5;
struct eg{int u,v,nx,w;}e[M];int head[N],tot;
inline void add(R int u,R int v,R int w){e[++tot]={u,v,head[u],w},head[u]=tot;}
struct node{int u,d;inline node(R int uu,R int dd):u(uu),d(dd){}inline bool operator <(const node &b)const{return d>b.d;}
};priority_queueq;
int dis[2][N],fa[N];bool vis[N],flag[M];
int n,m,res;
void dij(int *dis,int S){memset(dis,0x3f,(n+1)<<2);memset(vis,0,(n+1)<<2);dis[S]=0,q.push(node(S,0));while(!q.empty()){int u=q.top().u;q.pop();if(vis[u])continue;vis[u]=1;go(u)if(cmin(dis[v],dis[u]+e[i].w))q.push(node(v,dis[v]));}
}
vectorg[N];
void dfs(int u){for(int i=g[u].size()-1,v;~i;--i){v=g[u][i];dis[0][v]+dis[1][v]!=dis[0][n]?fa[v]=fa[u]:fa[v]=v;dfs(v);}
}
int main(){
//  freopen("testdata.in","r",stdin);n=read(),m=read(),res=inf;for(R int i=1,u,v,w;i<=m;++i)u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);dij(dis[0],1),dij(dis[1],n);fp(u,1,n)go(u)if(dis[1][u]==dis[1][v]+e[i].w)g[v].pb(u),flag[i]=1;fa[n]=n,dfs(n);for(R int i=1,u,v,w;i<=tot;++i){u=e[i].u,v=e[i].v,w=e[i].w;if(!flag[i]&&dis[0][u]<=dis[0][v]&&fa[u]!=fa[v]&&dis[0][u]+w+dis[1][v]!=dis[0][n])cmin(res,dis[0][u]+w+dis[1][v]);}printf("%d\n",res==inf?-1:res);return 0;
}

转载于:https://www.cnblogs.com/bztMinamoto/p/10706489.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！