Submission #3598105


Source Code Expand

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int inf=1<<29;
const int maxn=1e5+10;
int n,m,cnt;
int head[maxn];
struct Edge
{
    int v,c,nx;
}edge[maxn<<1];
struct Node
{
    int v,c;
};
int dis[maxn];
bool vis[maxn];

void _init() {
    cnt=0;
    memset(head,-1,sizeof(head));
}

inline void add(int u,int v,int c) {
    edge[cnt].v=v; edge[cnt].c=c;
    edge[cnt].nx=head[u];
    head[u]=cnt++;
    edge[cnt].v=u; edge[cnt].c=c;
    edge[cnt].nx=head[v];
    head[v]=cnt++;
}

void bfs() {
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;
    vis[1]=1;
    queue<Node> q;
    q.push(Node{1,0});
    while (!q.empty()) {
        Node t=q.front(); q.pop();
        int u=t.v;
        vis[u]=0;
        for (int i=head[u];i!=-1;i=edge[i].nx) {
            int v=edge[i].v;
            if (vis[v]) continue;
            if (t.c==edge[i].c && dis[v]>dis[u]) {
                dis[v]=dis[u];
                vis[v]=1;
                q.push(Node{v,edge[i].c});
            }
            if (t.c!=edge[i].c && dis[v]>dis[u]+1) {
                dis[v]=dis[u]+1;
                vis[v]=1;
                q.push(Node{v,edge[i].c});
            }
        }
    }
}

int main() {
    while (~scanf("%d%d",&n,&m)) {
        _init();
        int u,v,c;
        for (int i=1;i<=m;i++) {
            scanf("%d%d%d",&u,&v,&c);
            add(u,v,c);
        }
        bfs();
        printf("%d\n", dis[n]==inf?-1:dis[n]);
    }
    return 0;
}

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User vjudge1
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1526 Byte
Status RE
Exec Time 314 ms
Memory 3712 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:68:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d",&u,&v,&c);
                                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
AC × 5
WA × 9
RE × 45
Set Name Test Cases
Sample
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt
Case Name Status Exec Time Memory
01.txt AC 1 ms 768 KB
02.txt RE 126 ms 3456 KB
03.txt RE 132 ms 2944 KB
04.txt WA 83 ms 3200 KB
05.txt WA 56 ms 3328 KB
06.txt AC 29 ms 3456 KB
07.txt RE 125 ms 3456 KB
08.txt RE 130 ms 2944 KB
09.txt RE 127 ms 3456 KB
10.txt RE 126 ms 3456 KB
11.txt RE 126 ms 3456 KB
12.txt RE 124 ms 3456 KB
13.txt RE 125 ms 3456 KB
14.txt WA 48 ms 3456 KB
15.txt RE 126 ms 3456 KB
16.txt WA 56 ms 3456 KB
17.txt RE 124 ms 3456 KB
18.txt RE 124 ms 3456 KB
19.txt RE 126 ms 3456 KB
20.txt RE 124 ms 3456 KB
21.txt RE 128 ms 3712 KB
22.txt RE 126 ms 3584 KB
23.txt RE 127 ms 3456 KB
24.txt RE 127 ms 3584 KB
25.txt RE 125 ms 3456 KB
26.txt RE 125 ms 3456 KB
27.txt RE 126 ms 3456 KB
28.txt RE 127 ms 3456 KB
29.txt WA 70 ms 3456 KB
30.txt WA 52 ms 3456 KB
31.txt RE 125 ms 3456 KB
32.txt WA 60 ms 3456 KB
33.txt RE 124 ms 3456 KB
34.txt WA 60 ms 3456 KB
35.txt RE 125 ms 3456 KB
36.txt RE 126 ms 3584 KB
37.txt RE 126 ms 3456 KB
38.txt RE 128 ms 3456 KB
sample_01.txt AC 1 ms 768 KB
sample_02.txt AC 1 ms 768 KB
sample_03.txt AC 1 ms 768 KB
w1.txt WA 83 ms 3712 KB
w10.txt RE 131 ms 2944 KB
w11.txt RE 126 ms 3456 KB
w12.txt RE 128 ms 3456 KB
w13.txt RE 128 ms 3456 KB
w14.txt RE 129 ms 3456 KB
w15.txt RE 131 ms 3456 KB
w16.txt RE 127 ms 3456 KB
w17.txt RE 127 ms 3456 KB
w18.txt RE 130 ms 3456 KB
w2.txt RE 128 ms 3456 KB
w3.txt RE 314 ms 3456 KB
w4.txt RE 130 ms 3456 KB
w5.txt RE 131 ms 2944 KB
w6.txt RE 129 ms 3456 KB
w7.txt RE 127 ms 2944 KB
w8.txt RE 127 ms 2944 KB
w9.txt RE 128 ms 2944 KB