Coder Space

PKU 3463 Sightseeing --- 两点间最短路径和次短路径，条数和

题意很简单，给出图，找出从S到F两个点之间的最短路和比最短路长1的次短路的条数之和。

改进Dijkstra算法，。将状态扩展到二维，第一维仍然是顶点编号，第二维的长度为2，分别用于记录最短路和次短路。
这样的数据有两个，dist[][2]记录距离，cnt[][2]计数。

更新状态时：
1）新值小于最短路径长：更新最短路径长，计数；次短路径长，计数
2）新值等于最短路径长：更新最短路径计数
3）新值大于最短路径长，小于次短路径长：更新次短路径长，计数
4）新值等于次短路径长：更新次短路径计数

值得注意的是，题目图有重边，所以不能用邻接矩阵存储。

  1#include<iostream>
  2#include<limits>
  3#include<vector>
  4
  5using namespace std;
  6
  7const int maxN = 1001;
  8const int INF = numeric_limits<int>::max();
  9
 10//边结构，记录终点和边权
 11struct Node
 12{
 13    int e;
 14    int w;
 15};
 16
 17vector<Node> G[maxN];
 18int dist[maxN][2],cnt[maxN][2];             //二维距离和计数矩阵，0对应最短路，1对应次短路
 19
 20//改进Dijkstra算法，求最短路和次短路，并记录路径数
 21int Dijkstra(int n,int s,int f)
 22{
 23    bool flag[maxN][2];
 24
 25    for(int i=1;i<=n;i++)
 26    {
 27        flag[i][0] = false;
 28        flag[i][1] = false;
 29        dist[i][0] = INF;
 30        dist[i][1] = INF;
 31    }
 32    dist[s][0] = 0;
 33    cnt[s][0] = 1;
 34
 35    for(int i=0;i<2*n;i++)
 36    {
 37        int temp = INF;
 38        int u = -1;
 39        int k;        
 40
 41        for(int j=1;j<=n;j++)
 42        {
 43            if((!flag[j][0]) && (dist[j][0] < temp))
 44            {
 45                temp = dist[j][0];
 46                u = j;
 47                k = 0;
 48            }
 49            else if((!flag[j][1]) && (dist[j][1] < temp))
 50            {
 51                temp = dist[j][1];
 52                u = j;
 53                k = 1;
 54            }
 55        }
 56
 57        if(u == -1)
 58        {
 59            break;
 60        }
 61
 62        flag[u][k] = true;
 63
 64        //更新结点最短和次短路径，以及路径数目
 65        for(vector<Node>::iterator iter = G[u].begin(); iter != G[u].end(); iter++)
 66        {
 67            int newDist = dist[u][k] + iter->w;
 68            int j = iter->e;
 69            if(newDist < dist[j][0])
 70            {
 71                dist[j][1] = dist[j][0];
 72                cnt[j][1] = cnt[j][0];
 73
 74                dist[j][0] = newDist;
 75                cnt[j][0] = cnt[u][k];
 76            }
 77            else if(newDist == dist[j][0])
 78            {
 79                cnt[j][0] += cnt[u][k];
 80            }
 81            else if(newDist < dist[j][1])
 82            {
 83                dist[j][1] = newDist;
 84                cnt[j][1] = cnt[u][k];
 85            }
 86            else if(newDist == dist[j][1])
 87            {
 88                cnt[j][1] += cnt[u][k];
 89            }
 90        }
 91    }
 92
 93    int num = cnt[f][0];
 94    if(dist[f][0] + 1 == dist[f][1])
 95    {
 96        num += cnt[f][1];
 97    }
 98    return num;
 99}
100
101int main()
102{
103    int nCase;
104    int N,M;
105    int a;
106    int S,F;
107    Node node;
108
109    int i;
110
111    cin>>nCase;
112
113    while(nCase--)
114    {
115        cin>>N>>M;
116        
117        for(i=1;i<=N;i++)
118        {
119            G[i].clear();
120        }
121
122        for(i=0;i<M;i++)
123        {
124            cin>>a>>node.e>>node.w;
125            G[a].push_back(node);
126        }
127
128        cin>>S>>F;
129
130        cout<<Dijkstra(N,S,F)<<endl;
131    }
132}
133

posted on 2010-05-07 19:38 David Liu 阅读(1804) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论