颓了,,, 重边导致我乖乖用邻接矩阵....
好吧就是个最短路计数.... 如果更新时 d[v]==d[u]+w[i], 就可以接起来, 把两个加在一起..
如果 d[v]>d[u]+w[i], 那么 c[v] 直接赋值为 c[u], 相当于这个最短路是由 u 转移过来的,
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<queue>
- #define R register int
- using namespace std;
- const int N=2010,M=4000010;
- inline int g() {
- R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
- do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
- }
- int n,m,cnt;
- int w[N][N],fir[N],d[N],c[N];
- bool vis[N];
- priority_queue<pair<int,int>> q;
- inline void dijk() {
- memset(d,0x3f,sizeof(int)*(n+2)); c[1]=1,d[1]=0,q.push(make_pair(0,1));
- while(q.size()) {
- R u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=true;
- for(R i=1;i<=n;++i) {
- if(d[i]>d[u]+w[u][i]) d[i]=d[u]+w[u][i],q.push(make_pair(-d[i],i)),c[i]=c[u];
- else if(d[i]==d[u]+w[u][i]) c[i]+=c[u];
- }
- }
- }
- signed main() { freopen("in.in","r",stdin);
- n=g(),m=g(); memset(w,0x3f,sizeof(w)); for(R i=1,u,v,ww;i<=m;++i) u=g(),v=g(),ww=g(),w[u][v]=min(w[u][v],ww);
- dijk(); if(d[n]==0x3f3f3f3f) printf("No answer\n"); else printf("%d %d\n",d[n],c[n]);
- }
- 2019.04.24
来源: http://www.bubuko.com/infodetail-3034991.html