Submission #21310886

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}

void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,char>>> e(n);
    bool v[1000][1000]={};
    for(int i{},a,b;i<(m);++i){
        char c;
        cin>>a>>b>>c;--a,--b;
        v[a][b]=v[b][a]=true;
        e[a].emplace_back(b,c);
        e[b].emplace_back(a,c);
    }
    using ti = tuple<int,int,int>;
    priority_queue<ti, vector<ti>, greater<>> pq;
    vector<vector<bool>> cc(n,vector<bool>(n,false));
    pq.emplace(0,0,n-1);
    int ans{INT_MAX};
    while(!pq.empty()){
        auto[c,i,I]=pq.top();pq.pop();
        if(ans<=2*c) break;
        if(i==I){
            chmin(ans, 2*c);
            break;
        }
        if(v[i][I]){
            chmin(ans,2*c+1);
            continue;
        }
        for(auto[j,cj]:e[i]) for(auto[J,cJ]:e[I]) if(cj==cJ){
            if(cc[j][J]) continue;
            cc[j][J]=true;
            pq.emplace(c+1, j, J);
        }
    }
    cout<<(ans==INT_MAX?-1:ans)<<'\n';
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

Submission Info

Judge Result