AW349 黑暗城堡

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

题目地址

---

易错点：

• 模数是2147483647.

---

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int MAXN=2e3,MAXM=2e6,MOD=2147483647;
struct Edge{int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=0;
void addEdge(int u,int v,int w){e[++edgeCnt].from=u;e[edgeCnt].to=v;e[edgeCnt].w=w;e[edgeCnt].nxt=head[u];head[u]=edgeCnt;
}
int dis[MAXN];
struct Node{int v,d;bool operator <(Node another)const{return d>another.d;}
};
void dijkstra(){memset(dis,0x3f,sizeof(dis));priority_queue<Node> q;q.push(Node{1,0});dis[1]=0;while(!q.empty()){Node nowNode=q.top();q.pop();int v=nowNode.v,d=nowNode.d;if(d>dis[v])continue;for(int i=head[v];i;i=e[i].nxt){int nowV=e[i].to;if(dis[nowV]>dis[v]+e[i].w){dis[nowV]=dis[v]+e[i].w;q.push(Node{nowV,dis[nowV]});}}}
}
int cnt[MAXN];
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,l;scanf("%d%d%d",&x,&y,&l);addEdge(x,y,l);addEdge(y,x,l);}dijkstra();for(int x=1;x<=n;x++){for(int i=head[x];i;i=e[i].nxt){int nowV=e[i].to;if(dis[nowV]==dis[x]+e[i].w){cnt[nowV]+=1;}}}ll ans=1;for(int i=2;i<=n;i++){ans=ans*cnt[i]%MOD;}printf("%lld\n",ans);return 0;
}

 

这篇关于AW349 黑暗城堡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---