社区讨论

acwing上AC但洛谷30分,下载了数据后测试结果是对的,求调

P5767[NOI1997] 最优乘车参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo2sge3k
此快照首次捕获于
2023/10/23 19:02
2 年前
此快照最后确认于
2023/10/23 19:02
2 年前
查看原帖
CPP
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 5e2 + 10;
int n , m , g[N][N] , dist[N];
int stop[N];
int bfs()
{	
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	while(q.size())
	{
		int t = q.front();
		q.pop();
		//cout << t << ' ' << dist[t] << endl;
		for(int i = 1 ; i <= n ; i++){
			if(g[t][i] && dist[i] > dist[t] + 1){
				dist[i] = dist[t] + 1;
				q.push(i);
			}	
		}
	}
	return dist[n];
}
int main()
{
	cin >> m >> n;
	string road;
	memset(dist , 0x3f , sizeof dist);
	getchar();
	while(m--)
	{
		getline(cin , road);
		int cnt = 0;
		for(int i = 0 ; i < road.size() ; ++i) 
		{
			if(road[i] != ' ') {
				int res = 0;
				int j;
				for(j = i ; j < road.size() && road[j] != ' '; ++j){
					res = res * 10 + road[j] - '0';
				}
				i = j;
				stop[++cnt] = res;
			}
		}
		//for (int i = 1 ; i <= cnt ; ++i) cout << stop[i] << ' ';
		//cout << endl;
		for(int i = 1 ; i <= cnt ; ++i){
			for(int j = i + 1 ; j <= cnt ; ++j){
				g[stop[i]][stop[j]] = 1;
			}
		}
	}
	int ans = bfs();
	//cout << ans << endl;
	if(ans == 0x3f3f3f3f) puts("NO");
	else cout << ans - 1 << endl;
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...