NYOJ1238 最小换乘（dijkstra）-白红宇

NYOJ1238 最小换乘（dijkstra）

阅读量：5231 次

发布时间：2019-06-14

本文共 3056 字，大约阅读时间需要 10 分钟。

最少换乘

时间限制：2000 ms | 内存限制：65535 KB

难度：3

描述

欧洲某城是一个著名的旅游胜地，每年都有成千上万的人前来观光旅行。Dr. Kong决定利用暑假好好游览一番。。

年轻人旅游不怕辛苦，不怕劳累，只要费用低就行。但Dr. Kong年过半百，他希望乘坐BUS从住的宾馆到想去游览的景点，期间尽可量地少换乘车。

Dr. Kon买了一张旅游地图。他发现，市政部门为了方便游客，在各个旅游景点及宾馆，饭店等地方都设置了一些公交站并开通了一些单程线路。每条单程线路从某个公交站出发，依次途经若干个站，最终到达终点站。

但遗憾的是，从他住的宾馆所在站出发，有的景点可以直达，有的景点不能直达，则他可能要先乘某路BUS坐上几站，再下来换乘同一站的另一路BUS, 这样须经过几次换乘后才能到达要去的景点。

为了方便，假设对该城的所有公交站用1，2，……，N编号。Dr. Kong所在位置的编号为1，他将要去的景点编号为N。

请你帮助Dr. Kong寻找一个最优乘车方案,从住处到景点，中间换车的次数最少。

输入

第一行： K 表示有多少组测试数据。（2≤k≤8）

接下来对每组测试数据：

第1行: M N 表示有M条单程公交线路，共有N站。（1<=M<=100 1<N<=500）

第2~M+1行：每行描述一路公交线路信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。

输出

对于每组测试数据，输出一行，如果无法乘坐任何线路从住处到达景点，则输出"N0"，否则输出最少换车次数，输出0表示不需换车可以直达。

样例输入

23 76 74 7 3 62 1 3 52 61 3 52 6 4 3

样例输出

2NO

比赛的时候题目都没有看，以为是校赛的那道题(一直没有处理)，赛后看了原来不是那道题，这个应该是可以想出来的。

给出m条公交车线路，用字符串处理一下，存边。然后权值为1，d[n] - 1就是答案。

不过字符串处理是有点坑的。。。（可能是多位数。。。）

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
              10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                 
                   14 using namespace std; 15 #define rep(i,a,n) for (int i=a;i
                  
                   =a;i--) 17 #define pb push_back 18 #define mp make_pair 19 #define all(x) (x).begin(),(x).end() 20 #define fi first 21 #define se second 22 #define SZ(x) ((int)(x).size()) 23 #define FO freopen("in.txt", "r", stdin); 24 #define lowbit(x) (x&-x) 25 #define mem(a,b) memset(a, b, sizeof(a)); 26 typedef vector
                   
                     VI; 27 typedef long long ll; 28 typedef pair
                    
                      PII; 29 const ll mod=1000000007; 30 const int inf = 0x3f3f3f3f; 31 ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;} 32 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} 33 //head 34 35 const int maxn = 500 + 7; 36 int d[maxn]; 37 bool vis[maxn]; 38 int _, n, m; 39 char ss[100 * maxn];//注意范围 40 struct node{ 41 int v; 42 int dis; 43 node(){} 44 node(int _v, int _dis):v(_v), dis(_dis){} 45 }; 46 47 vector
                     
                       G[maxn]; 48 void dijkstra(int st) { //基操 49 fill(d, d+maxn, inf); 50 mem(vis, false); 51 d[st] = 0; 52 rep(i, 1, n+1) { 53 int minn = inf, u = -1; 54 rep(j, 1, n+1) { 55 if(d[j] < minn && !vis[j]) { 56 minn = d[j]; 57 u = j; 58 } 59 } 60 if(u == -1) return; 61 vis[u] = true; 62 rep(j, 0, SZ(G[u])) { 63 int v = G[u][j].v; 64 if(d[u] + G[u][j].dis < d[v] && !vis[v]) { 65 d[v] = d[u] + G[u][j].dis; 66 } 67 } 68 } 69 } 70 71 int main() { 72 for(scanf("%d", &_);_;_--) { 73 scanf("%d%d", &m, &n); 74 mem(G, 0); 75 getchar(); 76 while(m--) { 77 gets(ss); 78 int len = strlen(ss); 79 VI temp; 80 int zhi = 0; 81 rep(i, 0, len) { //把数据放入temp 82 if(ss[i] == ' ' || i == len - 1) { 83 if(i == len - 1) 84 zhi = zhi * 10 + ss[i] - '0'; 85 temp.pb(zhi); 86 zhi = 0; 87 } else zhi = zhi * 10 + ss[i] - '0'; 88 } 89 rep(i, 0, SZ(temp)) { //存边 90 rep(j, i+1, SZ(temp)) { 91 G[temp[i]].pb(node(temp[j], 1)); 92 } 93 } 94 } 95 dijkstra(1); 96 if(d[n] == inf) 97 printf("NO\n"); 98 else 99 printf("%d\n", d[n]-1);100 }101 }

转载于:https://www.cnblogs.com/ACMerszl/p/9572920.html

你可能感兴趣的文章