图论-生成树-黑暗城堡

本文主要是介绍图论-生成树-黑暗城堡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

没什么好说的，没有想清楚结果把计算ans数组时候用到的链式向前星的head写错了。。WA得还剩20分。
应该要写head[v[i].v]的，不能写head[i]，因为现在的第i个位置上放的已经不是原来的第i个点了。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define random(l,r) ((l)+rand()%((r)-(l)+1))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf=1e9+10,mod=2147483647,N=2222,M=2e6+10000;
const double eps=1e-6;
struct node{int v,dis;bool friend operator < (node a,node b){return a.dis<b.dis;}
}v[N];
int nxt[M],to[M],w[M],head[N],len;
int n,m,ans[N],pos[N];
bool vis[N];
ll anss=1;
inline void addedge(int a,int b,int ww){nxt[++len]=head[a]; head[a]=len; to[len]=b; w[len]=ww;
}
inline void Dijkstra(){rep(i,1,n) v[i].v=i,v[i].dis=inf;v[1].dis=0;rep(i,1,n-1){int now=inf,k=0;rep(j,1,n) if((vis[j]==false)&&(v[j].dis<now)) k=j,now=v[j].dis;vis[k]=true;for(int e=head[k];e!=0;e=nxt[e]) v[to[e]].dis=min(v[to[e]].dis,v[k].dis+w[e]);}
}
int main(){ios::sync_with_stdio(false); cin.tie(0);cin>>n>>m;rep(i,1,m){int a,b,w; cin>>a>>b>>w;addedge(a,b,w); addedge(b,a,w);}Dijkstra();//rep(i,1,n) printf("dis[%d]=%d\n",i,v[i].dis);sort(v+1,v+1+n);rep(i,1,n) pos[v[i].v]=i;//rep(i,1,n) printf("v[%d]=%d\n",i,v[i].v);ans[v[1].v]=1;rep(i,1,n){for(int e=head[v[i].v];e!=0;e=nxt[e]){if(v[pos[to[e]]].dis==v[i].dis+w[e]) ans[v[pos[to[e]]].v]++;}}rep(i,1,n) anss=(anss*(long long)(ans[i]>0?ans[i]:1))%mod;cout<<anss;return 0;
}