#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
#define l first
#define r second
typedef long long lint;
typedef pair<int, int> ii;
int mod[250005];
int rem[250005];
int label[250005];
int basic[250005];
int looped[250005];
vector<int> adj[250005];
vector<int> special[250005];
vector<int> dis[250005];
vector<ii> Q[1000005];
int uu[3000005];
int vv[3000005];
void addedge(int u, int v){
if(label[v] == 0) adj[u].push_back(v);
else special[u].push_back(v);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
//freopen("i.txt","r",stdin);
int n, m; cin >> n >> m;
for(int i = 1;i <= m;i++){
cin >> uu[i] >> vv[i];
}
for(int i = 1;i <= n;i++) mod[i] = 1, rem[i] = 1;
int K; cin >> K;
for(int i = 1;i <= K;i++){
int L; cin >> L;
for(int u = 0;u < L;u++){
int x; cin >> x;
mod[x] = L;
rem[x] = u;
label[x] = i;
}
}
for(int i = 1;i <= m;i++){
addedge(uu[i], vv[i]);
addedge(vv[i], uu[i]);
}
const int inf = 102345678;
for(int i = 1;i <= n;i++){
dis[i].resize(mod[i]);
fill(all(dis[i]), inf);
}
Q[0].push_back(ii(1,0));
for(int d = 0;d <= 300000;d++){
for(ii u : Q[d]){
int a = u.first, b = u.second;
if(d % mod[a] == rem[a]){
dis[a][b] = 0;
continue;
}
// show3(a,b,d);
dis[a][b] = d;
for(int v : special[a]){
if(looped[v]) continue;
for(int r = 1;r <= mod[v];r++){
if((d+r)%mod[a] == rem[a]){
if(rem[v] == (rem[a]+1)%mod[v] or label[a] != label[v]){
int rr = (d+r)%mod[v];
if(dis[v][rr] > d+r){
dis[v][rr] = d+r;
Q[d+r].push_back(ii(v, (d+r)%mod[v]));
}
}
break;
}
int rr = (d+r)%mod[v];
if(dis[v][rr] > d+r){
dis[v][rr] = d+r;
Q[d+r].push_back(ii(v, (d+r)%mod[v]));
}
if(label[v] == 0 or label[a] == label[v]) break;
}
looped[v] = true;
}
if(basic[a]) continue;
basic[a] = 1;
for(int v : adj[a]){
for(int r = 1;r <= mod[v];r++){
if((d+r)%mod[a] == rem[a]){
if(rem[v] == (rem[a]+1)%mod[v] or label[a] != label[v]){
int rr = (d+r)%mod[v];
if(dis[v][rr] > d+r){
dis[v][rr] = d+r;
Q[d+r].push_back(ii(v, (d+r)%mod[v]));
}
}
break;
}
int rr = (d+r)%mod[v];
if(dis[v][rr] > d+r){
dis[v][rr] = d+r;
Q[d+r].push_back(ii(v, (d+r)%mod[v]));
}
if(label[v] == 0 or label[a] == label[v]) break;
}
}
}
Q[d].clear();
}
cout << dis[n][0];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
43304 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
53360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
43348 KB |
Output is correct |
| 2 |
Incorrect |
114 ms |
53328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
43348 KB |
Output is correct |
| 2 |
Incorrect |
114 ms |
53328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
43348 KB |
Output is correct |
| 2 |
Incorrect |
114 ms |
53328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
43304 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
53360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
43304 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
53360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
43304 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
53360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
