Coder Space

PKU 1847 Tram --- 两点间最短路径


有联系之间的点建边，如果是第一个邻接点，边权为0，否则边权为1，Dijkstra求A到B的最短路径即为所求。

  1#include<iostream>
  2#include<limits>
  3
  4using namespace std;
  5
  6const int maxN = 101;
  7const int INF = numeric_limits<int>::max();
  8
  9int s[maxN][maxN];
 10
 11int Dijkstra(int n,int f, int t)
 12{
 13    bool flag[maxN];
 14    int dist[maxN];
 15    for(int i=1;i<=n;i++)
 16    {
 17        flag[i] = false;
 18        dist[i] = s[f][i];
 19    }
 20
 21    dist[f] = 0;
 22    flag[f] = true;
 23
 24    for(int i=1;i<n;i++)
 25    {
 26        int temp = INF;
 27        int u = f;
 28        for(int j=1;j<=n;j++)
 29        {
 30            if((!flag[j]) && dist[j] < temp)
 31            {
 32                temp = dist[j];
 33                u = j;
 34            }
 35        }
 36
 37        flag[u] = true;
 38
 39        if(u==t)
 40        {
 41            return dist[u];
 42        }
 43        else if(u==f)
 44        {
 45            return -1;
 46        }
 47
 48        for(int j=1;j<=n;j++)
 49        {
 50            if((!flag[j]) && (s[u][j] != INF))
 51            {
 52                int newDist = dist[u] + s[u][j];
 53                if(newDist < dist[j])
 54                {
 55                    dist[j] = newDist;
 56                }
 57            }
 58        }
 59    }
 60    return -1;
 61}
 62
 63
 64int main()
 65{
 66    int N,A,B;
 67    int k,t;
 68
 69    int i,j;
 70
 71    while(cin>>N>>A>>B)
 72    {
 73
 74        for(i=1;i<=N;i++)
 75        {
 76            for(j=1;j<=N;j++)
 77            {
 78                s[i][j] = INF;
 79            }
 80        }
 81
 82        for(i=1;i<=N;i++)
 83        {
 84            cin>>k;
 85            for(j=1;j<=k;j++)
 86            {
 87                cin>>t;
 88                if(j==1)
 89                {
 90                    s[i][t] = 0;
 91                }
 92                else
 93                {
 94                    s[i][t] = 1;
 95                }
 96            }
 97        }
 98
 99        cout<<Dijkstra(N,A,B)<<endl;
100    }
101    return 0;
102}
103

posted on 2010-05-04 23:44 David Liu 阅读(157) 评论(0)  编辑 收藏 引用 所属分类: 图论


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


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论