WAon#6#7
  • 板块P1346 电车
  • 楼主albertting
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/3/23 09:57
  • 上次更新2024/3/23 12:01:05
查看原帖
WAon#6#7
1024213
albertting楼主2024/3/23 09:57

rt

#include <bits/stdc++.h>
using namespace std;

int n, a, b, m, x, f[105][105], dis[100005];
bool vis[100005];

int main()
{
	memset(f, 0x7f, sizeof(f));
	memset(dis, 0x7f, sizeof(dis));
	//初始化
	scanf("%d %d %d", &n, &a, &b);
	//输入
	for(int i = 1; i <= n; i++) f[i][i] = 0;
	//原地不动就是0
	for(int i = 1; i <= n; i++)
    {
        scanf("%d", &m);
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &x);
            if(j == 1) f[i][x] = 0;
            else f[i][x] = 1;
        }
    }
    /*
        把边权记录下来
        第一个是0
        后面都是1
    */
    for(int i = 1; i <= n; i++) dis[i] = f[a][i];
    dis[a] = 0;
    /*
        把直达的点边权记录下来
        自己改成0
    */
    for(int i = 1; i <= n; i++)
    {
        int minn = 0x7f, k = 0;
        for(int j = 1; j <= n; j++)
			if(!vis[j] && dis[j] < minn)
			{
				minn = dis[j];
				k = j;
			}
        if(!k) break;
        vis[k] = true;
        for(int j = 1; j <= n; j++)
            if(!vis[j] && dis[j] > dis[k] + f[k][j])
                dis[j] = dis[k] + f[k][j];
    }
    if(dis[b] == 0x7f) printf("-1");
    else printf("%d", dis[b]);
}

2024/3/23 09:57
加载中...