本文主要是介绍hdu3191 How Many Paths Are There，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求次短路
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define eps 1e-6
#define ll long long
const int N=55;
const int M=2550;
using namespace std;struct node
{int v,w,next;
}e[M];int h,head[N],vis[N][2],d[N][2],cnt[N][2],n,m,s,en;void addedge(int a,int b,int c)
{e[h].v=b;e[h].w=c;e[h].next=head[a];head[a]=h++;
}void dij()
{int i,j,p,dis,flag,x,v,w;memset(d,0x3f,sizeof d);d[s][0]=0;memset(vis,0,sizeof vis);memset(cnt,0,sizeof cnt);cnt[s][0]=1;for(i=0;i<n+n;i++){flag=-1;p=0;dis=inf;for(j=0;j<n;j++){if(!vis[j][0]&&dis>d[j][0]){dis=d[j][0];p=j;flag=0;}else if(!vis[j][1]&&dis>d[j][1]){dis=d[j][1];p=j;flag=1;}}if(flag==-1) break;vis[p][flag]=1;for(x=head[p];x!=-1;x=e[x].next){v=e[x].v;w=e[x].w;if(d[v][0]>w+dis){d[v][1]=d[v][0];cnt[v][1]=cnt[v][0];d[v][0]=w+dis;cnt[v][0]=cnt[p][flag];}else if(d[v][0]==w+dis){cnt[v][0]+=cnt[p][flag];}else if(d[v][1]>w+dis){d[v][1]=w+dis;cnt[v][1]=cnt[p][flag];}else if(d[v][1]==w+dis)cnt[v][1]+=cnt[p][flag];}}
}int main()
{int a,b,c;while(~scanf("%d%d%d%d",&n,&m,&s,&en)){memset(head,-1,sizeof head);h=0;while(m--){scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);}dij();printf("%d %d\n",d[en][1],cnt[en][1]);}return 0;
}
这篇关于hdu3191 How Many Paths Are There的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
