社区讨论
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 条回复,欢迎继续交流。
正在加载回复...