本文主要是介绍poj 3463 Sightseeing（最短路+次短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=3463
大致题意：给出一个有向图，从起点到终点求出最短路和次短路的条数之和。
解法：
用到的数组：dis[i][0]:i到起点的最短路，dis[i][1]:i到起点的严格次短路
vis[i][0],vis[i][1]:同一维的vis数组，标记距离是否已确定
sum[i][0]:i到起点的最短路条数，sum[i][1]:i到起点的次短路条数
同一维dijkstra，内循环先找出最短的距离(次短路或最短路)d，然后枚举与该点相连的点：
if(d < 最小) 更新最小和次小，包括距离以及路径条数
else if(d == 最小) 更新最短路径条数
else if(d < 次小) 更新次小，包括次小距离路径条数
else if(d == 次小) 更新次小路径条数
同一维不同的是外层循环次数为2*n-1次，因为更新最小n-1次，更新次小n次。
邻接表建图
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 1<<28;
const int maxn = 1010;
const int maxm = 10010;int cnt,head[maxn];
struct node
{int v,w,next;
}edge[maxm];
int n,m;
int s,t;
int dis[maxn][2];
int vis[maxn][2];
int sum[maxn][2];void init()
{memset(head,-1,sizeof(head));cnt = 0;
}void add(int u, int v, int w)
{edge[cnt] = (struct node){v,w,head[u]};head[u] = cnt++;
}void dijkstra()
{for(int i = 1; i <= n; i++){dis[i][0] = INF;dis[i][1] = INF;}memset(vis,0,sizeof(vis));memset(sum,0,sizeof(sum));dis[s][0] = 0;sum[s][0] = 1;for(int i = 1; i <= 2*n-1; i++){int Min = INF,pos = -1,flag;for(int j = 1; j <= n; j++){if(!vis[j][0] && Min > dis[j][0]){Min = dis[j][0];pos = j;flag = 0;}else if(!vis[j][1] && Min > dis[j][1]){Min = dis[j][1];pos = j;flag = 1;}}if(pos == -1)break;vis[pos][flag] = 1;for(int j = head[pos]; j != -1; j = edge[j].next){int v = edge[j].v;int w = edge[j].w;if(dis[v][0] > dis[pos][flag] + w) //比最小要小{dis[v][1] = dis[v][0];sum[v][1] = sum[v][0];dis[v][0] = dis[pos][flag] + w;sum[v][0] = sum[pos][flag];}else if(dis[v][0] == dis[pos][flag] + w) //等于最小{sum[v][0] += sum[pos][flag];}else if(dis[v][1] > dis[pos][flag] + w) //比次小要小{dis[v][1] = dis[pos][flag] + w;sum[v][1] = sum[pos][flag];}else if(dis[v][1] == dis[pos][flag] + w) //等于次小{sum[v][1] += sum[pos][flag];}}}if(dis[t][1] == dis[t][0] + 1)sum[t][0] += sum[t][1];printf("%d\n",sum[t][0]);
}int main()
{int test;int u,v,w;scanf("%d",&test);while(test--){init();scanf("%d %d",&n,&m);for(int i = 0; i < m; i++){scanf("%d %d %d",&u,&v,&w);add(u,v,w);}scanf("%d %d",&s,&t);dijkstra();}return 0;
}
这篇关于poj 3463 Sightseeing（最短路+次短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
