洛谷P1346 电车【最短路】

题目：https://www.luogu.org/problemnew/show/P1346

题意：n个路口，每个路口有好几条轨道，默认指向给出的第一个路口。

如果要换到另外的轨道去需要按一次开关。问从a到b最少需要几次开关。

思路：可以把默认的路口的轨道权值设为0，其他的权值都是1，不通的权值都是inf。

然后跑一遍最短路。注意-1.

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<iostream>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n, a, b;

 const int maxn = ;

 int g[maxn][maxn];

 bool vis[maxn];

 int d[maxn];

 void dijkstra(int st)

 {

     memset(d, 0x3f, sizeof(d));

     d[st] = ;

     vis[st] = true;

     for(int i = ; i <= n; i++){

         if(i != st)d[i] = g[st][i];

     }

     for(int t = ; t < n; t++){

         int min = inf, minid;

         for(int i = ; i <= n; i++){

             if(!vis[i] && d[i] < min){

                 min = d[i];

                 minid = i;

             }

         }

         vis[minid] = true;

         for(int i = ; i <= n; i++){

             if(d[i] > min + g[minid][i]){

                 d[i] = min + g[minid][i];

             }

         }

     }

     return;

 }

 int main()

 {

     scanf("%d%d%d", &n, &a, &b);

     memset(g, 0x3f, sizeof(g));

     for(int i = ; i <= n; i++){

         int k, to;

         scanf("%d", &k);

         if(k){

             scanf("%d", &to);

             g[i][to] = ;

         }

         for(int j = ; j < k; j++){

             scanf("%d", &to);

             g[i][to] = ;

         }

     }

     dijkstra(a);

     if(d[b] > 1e9)printf("-1\n");

     else printf("%d\n", d[b]);

     return ;

 }

巴特西

洛谷P1346 电车【最短路】

最新文章

热门文章