Submission #3598233


Source Code Expand

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int inf=1<<29;
const int maxn=1e5+10;
const int maxm=2e5+10;
int n,m,cnt;
int head[maxn];
struct Edge
{
    int v,c,nx;
}edge[maxm<<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;
    queue<Node> q;
    q.push(Node{1,0});
    while (!q.empty()) {
        Node t=q.front(); q.pop();
        int u=t.v;
        if (vis[u]) continue;
        vis[u]=1;
        for (int i=head[u];i!=-1;i=edge[i].nx) {
            int v=edge[i].v;
            if (t.c==edge[i].c && dis[v]>dis[u]) {
                dis[v]=dis[u];
                q.push(Node{v,edge[i].c});
            }
            if (t.c!=edge[i].c && dis[v]>dis[u]+1) {
                dis[v]=dis[u]+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 vjudge2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1479 Byte
Status WA
Exec Time 70 ms
Memory 6656 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66: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 × 47
WA × 12
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 AC 52 ms 5376 KB
03.txt AC 70 ms 6144 KB
04.txt AC 51 ms 5760 KB
05.txt WA 65 ms 6272 KB
06.txt AC 30 ms 4736 KB
07.txt AC 32 ms 4736 KB
08.txt AC 63 ms 6144 KB
09.txt AC 33 ms 4736 KB
10.txt AC 33 ms 4736 KB
11.txt AC 50 ms 6400 KB
12.txt AC 46 ms 5376 KB
13.txt AC 48 ms 5632 KB
14.txt AC 52 ms 6656 KB
15.txt AC 49 ms 6144 KB
16.txt AC 51 ms 6528 KB
17.txt AC 50 ms 6400 KB
18.txt AC 49 ms 5504 KB
19.txt AC 52 ms 6528 KB
20.txt AC 51 ms 6400 KB
21.txt AC 54 ms 6272 KB
22.txt WA 53 ms 6400 KB
23.txt WA 55 ms 6400 KB
24.txt AC 50 ms 6272 KB
25.txt AC 45 ms 5376 KB
26.txt AC 47 ms 5632 KB
27.txt AC 52 ms 6400 KB
28.txt AC 52 ms 6400 KB
29.txt AC 50 ms 6400 KB
30.txt AC 50 ms 6400 KB
31.txt AC 45 ms 5504 KB
32.txt AC 50 ms 6272 KB
33.txt AC 51 ms 6400 KB
34.txt WA 50 ms 6272 KB
35.txt AC 43 ms 5376 KB
36.txt AC 47 ms 5632 KB
37.txt WA 56 ms 6528 KB
38.txt WA 51 ms 6272 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 55 ms 6272 KB
w10.txt AC 53 ms 5504 KB
w11.txt AC 45 ms 5376 KB
w12.txt AC 53 ms 5376 KB
w13.txt WA 54 ms 5376 KB
w14.txt AC 56 ms 5504 KB
w15.txt AC 45 ms 5376 KB
w16.txt AC 53 ms 5376 KB
w17.txt AC 54 ms 5376 KB
w18.txt WA 57 ms 5504 KB
w2.txt AC 55 ms 6144 KB
w3.txt AC 59 ms 6272 KB
w4.txt AC 55 ms 6272 KB
w5.txt AC 59 ms 6272 KB
w6.txt AC 56 ms 6272 KB
w7.txt WA 49 ms 5376 KB
w8.txt WA 57 ms 5376 KB
w9.txt WA 57 ms 5376 KB