| 比赛 |
NOIP2025模拟赛4 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
Daily Commute |
最终得分 |
100 |
| 用户昵称 |
特朗普 |
运行时间 |
5.212 s |
| 代码语言 |
C++ |
内存使用 |
19.05 MiB |
| 提交时间 |
2025-11-27 08:41:45 |
显示代码纯文本
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cstring>
#include<string>
#define int long long
using namespace std;
int n, m, i, j, k;
vector<int> G[200009];
bool vis[200009];
int dis[200009];
struct node
{
int pos, sta, dis;
bool operator<(node x)const
{
return x.dis < dis;
}
};
priority_queue<node> ans;
int a[200009];
map<int, int> pos;
signed main()
{
freopen("Commute.in" ,"r",stdin );
freopen("Commute.out","w",stdout);
cin >> n >> m >> k;
for (i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
G[v].push_back(u);
}
queue<int> q;
q.push(n);
vis[n] = 1;
memset(dis, 0x3f, sizeof(dis));
dis[n] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (!vis[v]) dis[v] = dis[u] + 1, q.push(v), vis[v] = 1;
}
}
for (i = 1; i <= n; i++) cin >> a[i], ans.push({ i,a[i],i + dis[a[i]] - 1}), pos[a[i]] = i;
int nc = dis[1];
while (k--)
{
int x, y;
cin >> x >> y;
int pp = pos[a[x]];
pos[a[x]] = pos[a[y]];
pos[a[y]] = pp;
ans.push({ x,a[y],x + dis[a[y]] - 1 });
ans.push({ y,a[x],y + dis[a[x]] - 1 });
swap(a[x], a[y]);
while (!ans.empty() && pos[ans.top().sta] != ans.top().pos) ans.pop();
cout << min({ ans.top().dis, nc ,pos[n] - 1 }) << endl;//car->walk, walk, car
}
return 0;
}