【BZOJ1576】[Usaco2009Jan]安全路径规划：最短路径算法与并查集应用

#include 
#include 
#include 
#include 
#include 
#include 
#define mp(A,B) make_pair(A,B)
using namespace std;
const int maxn=100010;
int n,m,cnt;
int to[maxn<<2],next[maxn<<2],val[maxn<<2],head[maxn],dis[maxn],fa[maxn],pre[maxn];
int f[maxn],s[maxn],ans[maxn];
bool vis[maxn];
priority_queue > q;
struct edge
{
int a,b,v;
bool ont;
}p[maxn<<1];
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd()
{
int ret=0,f=1;char gc=nc();
while(!isdigit(gc)){if(gc=='-')f=-f;gc=nc();}
while(isdigit(gc))ret=ret*10+gc-'0',gc=nc();
return ret*f;
}
inline void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
bool cmp(const edge &a,const edge &b)
{
return a.v}
int find(int x)
{
return (f[x]==x)?x:(f[x]=find(f[x]));
}
int main()
{
n=rd(),m=rd();
memset(head,-1,sizeof(head));
register int i,u,a,b;
for(i=1;i<=m;i++)p[i].a=rd(),p[i].b=rd(),p[i].v=rd(),add(p[i].a,p[i].b,p[i].v),add(p[i].b,p[i].a,p[i].v);
memset(dis,0x3f,sizeof(dis));
dis[1]=0,q.push(mp(0,1));
while(!q.empty())
{
u=q.top().second,q.pop();
if(vis[u])continue;
vis[u]=1;
for(i=head[u];i!=-1;i=next[i])if(dis[to[i]]>dis[u]+val[i])
fa[to[i]]=u,pre[to[i]]=(i>>1)+1,dis[to[i]]=dis[u]+val[i],q.push(mp(-dis[to[i]],to[i]));
}
for(i=1;i<=n;i++)f[i]=i,p[pre[i]].Ont=1;
for(i=1;i<=m;i++)p[i].v+=dis[p[i].a]+dis[p[i].b];
sort(p+1,p+m+1,cmp);
for(i=1;i<=m;i++)if(!p[i].ont)
{
a=find(p[i].a),b=find(p[i].b);
while(a!=b)
{
if(dis[a]ans[a]=p[i].v-dis[a],f[a]=fa[a],a=find(f[a]);
}
}
for(i=2;i<=n;i++)printf("%d\n",(!ans[i])?-1:ans[i]);
return 0;
}