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;
    }
    

    信息

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