正解:最短路+小学奥数 乘法原理
解题报告:
首先读懂题意(,,,我觉得我吃枣死于语文太差读不懂题目QAQ
大意就是港,要求从第一个点到其他各点的长度都是最短的方案有多少个(ummm,,,不知道表述清楚辽没有QAQ
那理解了大意就简单辣,不就是个小学奥数乘法原理嘛,然后剩下的实现过程和原理我昨儿写了一下直接贴过来辽
先跑一遍最短路,得到到每个点的dis
然后一个个点地看,看从它的邻点到它是最短路的有几个,然后ans*=个数
理解一下?
因为我有这么多个点过来,我就可以任取他们中的一条边留下其他的删了,然后根据小学奥数知识可以得到这相当于是分阶段那当然是乘法原理咯,乘一下就出来了
over
#include<bits/stdc++.h>#define N 57#define M 2507#define mod 1000000007#define ll long long#define inf 1000000007#define P pair<ll,ll>#define rp(i,x,y) for(register ll i=x;i<=y;++i)#define mp make_pairusing namespace std;ll n,head[N],dis[N],tot;struct ed{ll to,next,wei;}edge[M];bool vis[N];priority_queue< P,vector< P >,greater< P > >Q;inline ll read(){ ;; '))ch=getchar(); ; )+(x<<)+(ch^'),ch=getchar(); return y?x:-x;}inline void add(ll x,ll y,ll z){edge[++tot].to=x;edge[tot].next=head[y];edge[tot].wei=z;head[y]=tot;}inline void dij(){ memset(dis,/,,));vis[]=;dis[]=; while(!Q.empty()) { ll t=Q.top().second;Q.pop(); ;i=edge[i].next) if(dis[edge[i].to]>dis[t]+edge[i].wei) { dis[edge[i].to]=dis[t]+edge[i].wei; ; } }}int main(){ n=read(); rp(i,,n) rp(j,,n){');} dij(); ll ans=; ;i<=n;i++) { ll tott=; ;j=edge[j].next) { int t1=edge[j].to,t2=edge[j].wei; if (dis[i]==dis[t1]+t2) tott++; } ans=(ans*tott)%mod; } printf("%lld",ans);}
哭辽?为什么我的代码这么丑别的大佬代码那么帅啊QAQ
这个还是,比较新手村的?overrrr
完美结束yeah
