列表

详情

NC214737. 拯救公主

描述

“影子传说传说着一个斗士”
“金色战盔散发出无限的能量”
“影子斗士是来自正义的化身”
“……”
影从邪恶忍者的营地里救下了被绑架的 Kiri 公主，但是不幸遭到了邪恶忍者的追杀。影曾经在一个遗迹中获得过一张传送卷轴，但是因为这张卷轴过于古老，已经失去了原有的功能，只能传送到某一些结点，并且只有一次使用机会，但是可以在这些结点中自由选择。
地图上的共有 n 个结点，标记为 ，以及 m 条双向道路，每条路连接两个结点。任意一条道路的长度都默认为 1。
影的传送卷轴一共能传送到 p 个结点，结点集合为 P。在地图上有 q 个安全区结点，结点集合为 Q。
由于影在使用完传送卷轴后会失去战斗力，需要迅速带着公主前往最近的安全区。
请你帮他寻找一条最短的前往任意安全区的路径，输出路径和。

输入描述

第 1 行，包含两个整数 n 和 m 分别表示结点个数和连接结点的路径数。
第 2 行，包含两个整数 p 和 q 分别表示传送卷轴能够到达的结点数量和安全区的数量 。
第 3 行，包含 p 个整数 ，表示传送卷轴能够到达的结点编号。
第 4 行，包含 q 个整数 ，表示安全区的结点编号。
第  行，每行包含 2 个整数 u,v，表示结点 u 和 v 之间存在一条长度为 1 的双向道路 。

输出描述

输出一个整数表示使用传送卷轴后去最近的安全区的距离，若无法到达，则输出"-1"。

示例1

输入: 

5 6
1 1
2
3
1 2
1 3
1 4
2 5
3 5
4 5

输出: 

2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 373ms, 内存消耗: 23200K, 提交时间: 2022-11-29 11:20:37 

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y, a, b;
vector<int>G[MAX];

queue<int>q;
set<int>se;
int dis[MAX];

void bfs(){
    while(!q.empty()){
        int u = q.front();q.pop();
        if(se.count(u)){
            cout << dis[u] << endl;
            return;
        }
        for(auto v : G[u]){
            if(dis[v] != inf)continue;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
    cout << -1 << endl;
}

void work(){
    cin >> n >> m;
    mem(dis, inf);
    cin >> a >> b;
    for(int i = 1; i <= a; ++i){
        cin >> x;
        q.push(x);
        dis[x] = 0;
    }
    for(int i = 1; i <= b; ++i){
        cin >> x;
        se.insert(x);
    }
    for(int i = 1; i <= m; ++i){
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    bfs();
}


int main(){
    io;
    work();
    return 0;
}

C++(clang++11) 解法, 执行用时: 358ms, 内存消耗: 17784K, 提交时间: 2020-12-26 13:07:44 

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

struct node
{
	int x,h;
}Q[100005];
vector<int>R[100005];
bool flag=0,V[100005]={0},T[100005]={0};
int main()
{
    int i,j,n,m,p,q,r=0,f=0,x,h;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    while(p--)scanf("%d",&i),V[i]=1,Q[r].x=i,Q[r++].h=0;
	while(q--)scanf("%d",&i),T[i]=1;
	while(m--)
	{
		scanf("%d%d",&i,&j);
		R[i].push_back(j),R[j].push_back(i);
	}
	while(r!=f)
	{
		x=Q[f].x,h=Q[f++].h;
		if(T[x]){flag=1;break;}
		for(i=0;i<R[x].size();i++)
		{
			j=R[x][i];
			if(!V[j])V[j]=1,Q[r].x=j,Q[r++].h=h+1;
		}
	}
	if(!flag)h=-1;
	printf("%d\n",h);
    return 0;
}

上一题

© 2024 nowcoder.com