#include #include #include #include using namespace std; int n, m, x, y, z, Q, vrt, q1, q2, curr; queue q; bool allow[100001], used[100001]; vector > v[100001]; int l1[100001], l2[100001], parent1[100001]; int solve(int q1, int q2) { while(!q.empty()) { q.pop(); } for(int i=1; i<=n; ++i) { used[i]=false; } q.push(q1); l1[q1]=0; used[q1]=true; while(!q.empty()) { curr=q.front(); q.pop(); if(curr==q2) { break; } for(int i=0; i<(int)v[curr].size(); ++i) { if(!used[v[curr][i].first]) { used[v[curr][i].first]=true; parent1[v[curr][i].first]=curr; l1[v[curr][i].first]=(l1[curr] || !allow[curr]? l1[curr]+v[curr][i].second: l1[curr]); q.push(v[curr][i].first); } } } while(!q.empty()) { q.pop(); } for(int i=1; i<=n; ++i) { used[i]=false; } q.push(q2); l2[q2]=0; used[q2]=true; while(!q.empty()) { curr=q.front(); q.pop(); if(curr==q1) { break; } for(int i=0; i<(int)v[curr].size(); ++i) { if(!used[v[curr][i].first]) { used[v[curr][i].first]=true; l2[v[curr][i].first]=(l2[curr] || !allow[curr]? l2[curr]+v[curr][i].second: l2[curr]); q.push(v[curr][i].first); } } } int idx, res=1000000000; for(idx=q2; idx!=q1; idx=parent1[idx]) { res=min(l1[idx]+l2[idx], res); } res=min(l1[idx]+l2[idx], res); return res; } int main () { //freopen("3001.txt", "r", stdin); freopen("voyage.in", "r", stdin); freopen("voyage.out", "w", stdout); //ios::sync_with_stdio(false); //cin.tie(NULL); scanf("%d", &n); for(int i=0; i