Submission #3598363

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#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,w;
    bool operator <(const Node&n1) const {
        return w==n1.w?v<n1.v:w<n1.w;
    }
};
int dis[maxn];
bool vis[maxn];
set<int> col[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++) col[i].clear();
    for (int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;
    priority_queue<Node> q;
    q.push(Node{1,0});
    while (!q.empty()) {
        Node t=q.top(); 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;
            int w=col[u].count(edge[i].c)?0:1;
            if (dis[v]>dis[u]+w) {
                dis[v]=dis[u]+w;
                col[v].clear();
                col[v].insert(edge[i].c);
                q.push(Node{v,-dis[v]});
            } else if (dis[v]==dis[u]+w) {
                col[v].insert(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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73: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