描述
你知道黑暗城堡有 NN 个房间, MM 条可以制造的双向通道, 以及每条通道的长度.
城堡是树形的并且满足下面的条件:
设 DiDi 为如果所有的通道都被修建, 第 ii 号房间与第 11 号房间的最短路径长度;
而 SiSi 为实际修建的树形城堡中第 ii 号房间与第 11 号房间的路径长度;
要求对于所有整数 ii (1iN1iN), 有 Si=DiSi=Di 成立.
你想知道有多少种不同的城堡修建方案. 当然, 你只需要输出答案对 231?1231?1 取模之后的结果就行了.
输入
第一行为两个由空格隔开的整数 N,MN,M;
第二行到第 M+1M+1 行为 33 个由空格隔开的整数 x,y,lx,y,l: 表示 xx 号房间与 yy 号房间之间的通道长度为 ll.
输出
一个整数: 不同的城堡修建方案数对 231?1231?1 取模之后的结果.
样例输入
4 6 1 2 1 1 3 2 1 4 3 2 3 1 2 4 2 3 4 1
样例输出
6
咳咳, 我觉得这道题定三级实在有点过分 (因为我现在也很糊)
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<queue>
- #define inf 0x3f3f3f3f3f3f
- #define ll long long
- #define modd 2147483647
- using namespace std;
- ll read(){
- ll x=0,f=1;char ch;
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
- return x*f;
- }
- struct node{
- ll u,v,w,nxt;
- }e[2000101];
- struct node2{
- ll w,id;
- }dis[100101];
- ll fir[1000101],cnt=0;
- ll n,m,s,ed;
- ll vis[1000101];
- ll pos[1001][1001];
- struct edge{
- ll u,dis;
- bool operator <(const edge& lala)const{
- return dis>lala.dis;
- }
- };
- void add(ll x,ll y,ll z){
- e[++cnt].nxt=fir[x];e[cnt].u=x;e[cnt].v=y;e[cnt].w=z;fir[x]=cnt;
- }
- void dijis(ll st){
- priority_queue<edge> q;
- for(ll i=1;i<=n;i++)dis[i].w=inf,dis[i].id=i;
- dis[st].w=0;dis[st].id=1;q.push((edge){st,0});
- while(!q.empty()){
- edge x=q.top();q.pop();
- ll u=x.u,d=x.dis;
- if(d!=dis[u].w)continue;
- for(ll i=fir[u];i;i=e[i].nxt){
- ll v=e[i].v,uu=e[i].u;
- if(dis[v].w>dis[uu].w+e[i].w){
- dis[v].w=e[i].w+dis[uu].w;
- q.push((edge){v,dis[v].w});
- }
- }
- }
- }
- bool cmp(node2 a,node2 b){
- return a.w<b.w;
- }
- int main(){
- scanf("%lld%lld",&n,&m);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)pos[i][j]=inf;
- for(ll i=1;i<=m;i++){
- ll x,y,z;
- x=read(),y=read(),z=read();
- add(x,y,z); add(y,x,z);
- pos[x][y]=pos[y][x]=min(pos[x][y],z);
- }
- dijis(1);
- //for(int i=1;i<=n;i++)cout<<dis[i].w<<' ';
- sort(dis,dis+n+1,cmp);
- ll ans=1;
- for(int i=2;i<=n;i++){
- ll tot=0;
- for(int j=1;j<i;j++){
- ll uu=dis[i].id,vv=dis[j].id;
- if(dis[i].w==dis[j].w+pos[uu][vv])tot++;
- }
- ans=ans*tot%modd;
- }
- printf("%lld",ans);
- return 0;
- }
其实呢, 这个代码是错的 别急啊, 思路肯定是对的, 最短路 + 不带合并的生成树 因为数据范围小我们可以暴力统计直接使用乘法原理 所以先求出最短路径 dis[i], 记录 dis[i[是哪个点的最短路径 id; 把满足 dis[x]=dis[y]+pos[i][j] 的一个个点的往生成树之中加 再根据乘法原理求出答案 然后? 然后就错了....(雾)
来源: http://www.bubuko.com/infodetail-2755108.html