本文主要是介绍poj-3463-Sightseeing-求次短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意是求最短路的数量和比最短路长1的路的数量。
此题的本质就是在dij的过程中，可以把一个点走两次。一次最短，一次次短。
最后判断即可。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define maxn 210000
#define maxeg 22000
#define maxpt 2001
#define INF 99999999
struct G
{int num;int head[maxpt];struct list{int u,v,w,next;}edge[maxeg];void init(){memset(head,-1,sizeof(head));num=0;}void add(int u,int v,int w){edge[num].u=u;edge[num].v=v;edge[num].w=w;edge[num].next=head[u];head[u]=num++;}
}gra,fgra;
int n,m;
//priority_queue<list>que;
void dij(int x,int y)
{int i;int dis[maxpt][2];int vis[maxpt][2];int num[maxpt][2];for(i=0;i<=n;i++){dis[i][0]=dis[i][1]=INF;vis[i][0]=vis[i][1]=0;num[i][0]=num[i][1]=0;}dis[x][0]=0;num[x][0]=1;while(1){int minn=INF;int ip;int leap;for(i=1;i<=n;i++){if(!vis[i][0]){if(minn>dis[i][0]){minn=dis[i][0];ip=i;leap=0;}}if(!vis[i][1]){if(minn>dis[i][1]){minn=dis[i][1];ip=i;leap=1;}}}if(minn==INF)break;vis[ip][leap]=1;//cout<<ip<<" "<<leap<<" "<<minn<<endl;for(i=gra.head[ip];i!=-1;i=gra.edge[i].next){int v=gra.edge[i].v;int w=gra.edge[i].w;// cout<<v<<" "<<w<<endl;if(!vis[v][0]&&dis[v][0]>=dis[ip][leap]+w){if(dis[v][0]==dis[ip][leap]+w)num[v][0]+=num[ip][leap];else{dis[v][1]=dis[v][0];num[v][1]=num[v][0];dis[v][0]=dis[ip][leap]+w;num[v][0]=num[ip][leap];}}else if(!vis[v][1]&&dis[v][1]>=dis[ip][leap]+w){if(dis[v][1]==dis[ip][leap]+w)num[v][1]+=num[ip][leap];else{dis[v][1]=dis[ip][leap]+w;num[v][1]=num[ip][leap];}}}}int ans=0;if(dis[y][0]==dis[y][1]-1){ans=num[y][0]+num[y][1];}else ans=num[y][0];cout<<ans<<endl;
}
int main()
{int i,a,b,c,s,t,k;int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);gra.init();for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);gra.add(a,b,c);}scanf("%d%d",&s,&t);dij(s,t);}return 0;
}
这篇关于poj-3463-Sightseeing-求次短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
