Submission #2861172

---

Source Code Expand

#include <bits/stdc++.h>
#define N 100005

using namespace std;
typedef pair<int,int> ii;
struct data
{
    int dist,u,company;
};
map<int,int> d[N];
vector<vector<ii>> AdjList(N);

void dijistra()
{
    d[1][0] = 0;
    deque<data> q;
    q.push_back(data{0,1,0});

    while(!q.empty())
    {
        data f = q.front();
        q.pop_front();

        int dist = f.dist,u = f.u,c = f.company;
        if(dist!=d[u][c])
            continue;

        if(!d[u].count(0)||d[u].count(0)&&d[u][0]>dist)
        {
            d[u][0] = dist;
            q.push_front(data{dist,u,0});
        }

        if(c)
        {
            int pos = lower_bound(AdjList[u].begin(),AdjList[u].end(),ii(c,0)) - AdjList[u].begin() ;
            while(pos<AdjList[u].size()&&AdjList[u][pos].first==c)
            {
                int v = AdjList[u][pos].second;
                if(!d[v].count(c)||d[v].count(c)&&d[v][c]>dist)
                {
                    d[v][c] = dist;
                    q.push_front(data{dist,v,c});
                }
                pos++;
            }
        }
        else
        {
            for(auto i:AdjList[u])
            {
                int v = i.second,company = i.first;
                if(!d[v].count(company)||d[v].count(company)&&d[v][company]>dist+1)
                {
                    d[v][company] = dist+1;
                    q.push_back(data{dist+1,v,company});
                }
            }
        }
    }
}

signed main()
{
    int n,m;
    cin>>n>>m;

    while(m--)
    {
        int u,v,c;
        cin>>u>>v>>c;
        AdjList[u].push_back(ii(c,v));
        AdjList[v].push_back(ii(c,u));
    }

    for(int i=1;i<=n;i++)
        sort(AdjList[i].begin(),AdjList[i].end());

    dijistra();

    if(!d[n].count(0))
        cout<<-1;
    else
        cout<<d[n][0];
}

Submission Info

Judge Result