2 条题解

  • 0
    @ 2025-2-14 21:51:03

    把每个车站看作一个点,将这个车站相连的第一个边设为0,其余为1. 跑一边最短路,累加即可。

    #include <bits/stdc++.h>
    using namespace std;
    int n, m, k, A, B, d[105][105];
    
    int main() {
    	memset (d, 0x3f, sizeof(d));
    	cin >> n >> A >> B;
    	for (int i = 0; i <= n; i++)
    		d[i][i] = 0;
    	for (int i = 1; i <= n; i++) {
    		cin >> k;
    		for (int j = 1; j <= k; j++) {
    			cin >> m;
    			if (j == 1)
    				d[i][m] = 0;
    			else
    				d[i][m] = 1;
    		}
    	}
    	for (int k = 1; k <= n; k++)
    		for (int i = 1; i <= n; i++)
    			for (int j = 1; j <= n; j++)
    				d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
    	if (d[A][B] == 0x3f3f3f3f)
    		cout << -1;
    	else
    		cout << d[A][B];
    	return 0;
    }
    
    • 0
      @ 2025-2-14 21:51:01

      把每个车站看作一个点,将这个车站相连的第一个边设为0,其余为1. 跑一边最短路,累加即可。

      #include <bits/stdc++.h>
      using namespace std;
      int n, m, k, A, B, d[105][105];
      
      int main() {
      	memset (d, 0x3f, sizeof(d));
      	cin >> n >> A >> B;
      	for (int i = 0; i <= n; i++)
      		d[i][i] = 0;
      	for (int i = 1; i <= n; i++) {
      		cin >> k;
      		for (int j = 1; j <= k; j++) {
      			cin >> m;
      			if (j == 1)
      				d[i][m] = 0;
      			else
      				d[i][m] = 1;
      		}
      	}
      	for (int k = 1; k <= n; k++)
      		for (int i = 1; i <= n; i++)
      			for (int j = 1; j <= n; j++)
      				d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
      	if (d[A][B] == 0x3f3f3f3f)
      		cout << -1;
      	else
      		cout << d[A][B];
      	return 0;
      }
      
      • 1

      信息

      ID
      5404
      时间
      1000ms
      内存
      125MiB
      难度
      3
      标签
      递交数
      11
      已通过
      3
      上传者