#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dat{
int s, e, m; ll d;
dat(){}
dat(int s, int e, int m, ll d): s(s), e(e), m(m), d(d){}
bool operator<(const dat &r)const{
return d>r.d;
}
};
int n, m, s, t;
int idx[128];
vector<int> link[202][8];
vector<int> revLink[202][8];
ll dist[202][202][5];
bool chk[202][202][5];
priority_queue<dat> pq;
int main(){
idx['('] = 0, idx['['] = 1, idx['{'] = 2, idx['<'] = 3;
idx[')'] = 4, idx[']'] = 5, idx['}'] = 6, idx['>'] = 7;
scanf("%d %d %d %d", &n, &m, &s, &t);
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=0; k<5; k++) dist[i][j][k] = 1e18;
for(int i=1; i<=m; i++){
int x, y; char c;
scanf("%d %d %c", &x, &y, &c);
link[x][idx[c]].push_back(y);
revLink[y][idx[c]].push_back(x);
}
for(int i=1; i<=n; i++){
for(int j=0; j<8; j++){
sort(link[i][j].begin(), link[i][j].end());
link[i][j].erase(unique(link[i][j].begin(), link[i][j].end()), link[i][j].end());
sort(revLink[i][j].begin(), revLink[i][j].end());
revLink[i][j].erase(unique(revLink[i][j].begin(), revLink[i][j].end()), revLink[i][j].end());
for(auto x: link[i][j]){
if(j>=4) continue;
dist[i][x][j+1] = 1;
pq.push(dat(i, x, j+1, 1));
}
}
}
// for(int i=1; i<=n; i++){
// dist[i][i][0] = 0;
// pq.push(dat(i, i, 0, 0));
// }
while(!pq.empty()){
dat tmp = pq.top(); pq.pop();
if(chk[tmp.s][tmp.e][tmp.m]) continue;
chk[tmp.s][tmp.e][tmp.m] = 1;
if(tmp.s == s && tmp.e == t && tmp.m == 0){
printf("%lld\n", tmp.d);
return 0;
}
if(tmp.m){
tmp.m--;
for(auto v: link[tmp.e][tmp.m+4]){
ll nd = tmp.d + 1;
if(nd >= dist[tmp.s][v][0]) continue;
dist[tmp.s][v][0] = nd;
pq.push(dat(tmp.s, v, 0, nd));
}
continue;
}
for(int i=1; i<=n; i++){
if(chk[tmp.s][i]) continue;
ll nd = tmp.d + dist[tmp.e][i][0];
if(nd >= dist[tmp.s][i][0]) continue;
dist[tmp.s][i][0] = nd;
pq.push(dat(tmp.s, i, 0, nd));
}
for(int k=0; k<4; k++){
for(auto v: revLink[tmp.s][k]){
ll nd = tmp.d + 1;
if(nd >= dist[v][tmp.e][k+1]) continue;
dist[v][tmp.e][k+1] = nd;
pq.push(dat(v, tmp.e, k+1, nd));
}
}
}
printf("-1");
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:34:21: warning: array subscript has type 'char' [-Wchar-subscripts]
34 | link[x][idx[c]].push_back(y);
| ^
Main.cpp:35:24: warning: array subscript has type 'char' [-Wchar-subscripts]
35 | revLink[y][idx[c]].push_back(x);
| ^
Main.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%d %d %d %d", &n, &m, &s, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d %d %c", &x, &y, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
2380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
