Submission #2860746

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 2e5 + 10;
const int oo = 1e9;

struct state{ int dist, u, ci; };
int n, m;
map<int, int> dp[N];
vector<ii> vi[N];

void solve()    {
    deque<state> pq;
    pq.push_back({0, 1, 0});

    while(!pq.empty())  {
        state cur = pq.front(); pq.pop_front();
        int u = cur.u, ci = cur.ci;

        if(!dp[u].count(0) || (dp[u][0] > cur.dist) ){
            dp[u][0] = cur.dist; pq.push_back({cur.dist, u, 0});
        }

        if(ci)  {
            int pos = lower_bound(vi[u].begin(), vi[u].end(), ii(ci, 0)) - vi[u].begin();
            while(pos < vi[u].size() && vi[u][pos].fi == ci)    {
                int v = vi[u][pos].se;
                if(!dp[v].count(ci) || dp[v][ci] > cur.dist)    {
                    dp[v][ci] = cur.dist; pq.push_front({cur.dist, v, ci});
                }
                pos ++;
            }
        } else {
            for(ii v: vi[u])    {
                if(!dp[v.se].count(v.fi) || dp[v.se][v.fi] > cur.dist + 1)  {
                    dp[v.se][v.fi] = cur.dist + 1;
                    pq.push_back({cur.dist + 1, v.se, v.fi});
                }
            }
        }
    }
    int ans = oo;
    for(auto v: dp[n])  ans = min(ans, v.se);
    if(ans == oo) printf("-1");
    else printf("%d", ans);
}

signed main()
{
	//freopen("test.inp", "r", stdin);
	scanf("%d%d", &n, &m);
	FOR(i, 1, m)    {
        int u, v, ci; scanf("%d%d%d", &u, &v, &ci);
        vi[u].pb(ii(i, v));
        vi[v].pb(ii(i, u));
	}
	for(int i = 1; i <= n; ++i) sort(vi[i].begin(), vi[i].end());
	solve();
}

Submission Info

Compile Error

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

Judge Result