Description

多组询问，无向图上删除一条边后从 \(1\) 到 \(n\) 的最短路。

Solution

建立源点为 \(1\) 和 \(n\) 的最短路径树 \(T_1,T_n\)，要保证两课树上从 \(1\) 到 \(n\) 的路径相同。

不在从 \(1\) 到 \(n\) 的最短路径上的边可以覆盖最短路径上的一个区间，区间的左端点是 \(n\) 与 \(x\) 在 \(T_1\) 上的 LCA，而右端点是 \(1\) 与 \(y\) 在 \(T_n\) 上的 LCA。

若删除了最短路径上的边，则可以选择一个包含该边的区间来替换。

Code

#define LOCAL
#include "bits/stdc++.h"
using namespace std;
using ui=unsigned; using db=long double; using ll=long long; using ull=unsigned long long; using lll=__int128;
using pii=pair<int,int>; using pll=pair<ll,ll>;
template<class T1, class T2> istream &operator>>(istream &cin, pair<T1, T2> &a) { return cin>>a.first>>a.second; }
template <std::size_t Index=0, typename... Ts> typename std::enable_if<Index==sizeof...(Ts), void>::type tuple_read(std::istream &is, std::tuple<Ts...> &t) { }
template <std::size_t Index=0, typename... Ts> typename std::enable_if<Index < sizeof...(Ts), void>::type tuple_read(std::istream &is, std::tuple<Ts...> &t) { is>>std::get<Index>(t); tuple_read<Index+1>(is, t); }
template <typename... Ts>std::istream &operator>>(std::istream &is, std::tuple<Ts...> &t) { tuple_read(is, t); return is; }
template<class T1> istream &operator>>(istream &cin, vector<T1> &a) { for (auto &x:a) cin>>x; return cin; }
template<class T1> istream &operator>>(istream &cin, valarray<T1> &a) { for (auto &x:a) cin>>x; return cin; }
template<class T1, class T2> bool cmin(T1 &x, const T2 &y) { if (y<x) { x=y; return 1; } return 0; }
template<class T1, class T2> bool cmax(T1 &x, const T2 &y) { if (x<y) { x=y; return 1; } return 0; }
istream &operator>>(istream &cin, lll &x) { x=0; static string s; cin>>s; for (char c:s) x=x*10+(c-'0'); return cin; }
ostream &operator<<(ostream &cout, lll x) { static char s[60]; int tp=1; s[0]='0'+(x%10); while (x/=10) s[tp++]='0'+(x%10); while (tp--) cout<<s[tp]; return cout; }
#if !defined(ONLINE_JUDGE)&&defined(LOCAL)
#include "my_header/IO.h"
#include "my_header/defs.h"
#else
#define dbg(...) ;
#define dbgx(...) ;
#define dbg1(x) ;
#define dbg2(x) ;
#define dbg3(x) ;
#define DEBUG(msg) ;
#define REGISTER_OUTPUT_NAME(Type, ...) ;
#define REGISTER_OUTPUT(Type, ...) ;
#endif
#define all(x) (x).begin(),(x).end()
#define print(...) cout<<format(__VA_ARGS__)
#define println(...) cout<<format(__VA_ARGS__)<<'\n'
#define err(...) cerr<<format(__VA_ARGS__)
#define errln(...) cerr<<format(__VA_ARGS__)<<'\n'
const int mod = 998244353;
inline int fpow(int x,ll y,int m=mod){int r=1;for(;y;y>>=1,x=(ll)x*x%m)if(y&1)r=(ll)r*x%m;return r;}
inline int Add(int x, int y){return (x + y) % mod;}
inline int Mul(int x, int y){return 1ll * x * y % mod;}
inline int Dec(int x, int y){return (x+mod-y)%mod;}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cout<<fixed<<setprecision(15);
	int n, m, q;
    cin >> n >> m >> q;
    vector<tuple<int, int, int>> e(m);
    cin >> e;
    vector<int> que(q); cin >> que;
    vector Gs(n+1, vector<tuple<int,int,int>>());
    int id=0;
    for(auto [x, y, w] : e) 
        Gs[x].push_back({y, w, id}),
        Gs[y].push_back({x, w, id++});
  
  
    auto dj = [&](int S) -> vector<ll>
    {
        vector<ll> d(n+1, 1e18);
        d[S]=0;
        priority_queue<pair<ll,int>> q; q.push({0, S});
        while(q.size())
        {
            auto [D, x] = q.top(); q.pop(); D = -D;
            if (D > d[x]) continue;
            for(auto [y, w, id] : Gs[x])
            {
                if(cmin(d[y], D+w)) q.push({-d[y], y});
            }
        }
        return d;
    };
  
    vector<ll> ds=dj(1), dt=dj(n);
  
    if(ds[n]==1e18)
    {
        for(auto x : que) cout << "-1\n";
        return 0;
    }
  
    vector<pii> fs(n+1, {-1, -1}), ft(n+1, {-1, -1});
  
    queue<int> tmp;
    auto sol = [&](auto& d, auto& fa)
    {
        while(tmp.size())
        {
            int x=tmp.front(); tmp.pop();
            for(auto [y, w, id] : Gs[x]) if(fa[y].first==-1 && d[y]==d[x]+w)
            {
                fa[y]={x, id}; tmp.push(y);
            }
        }
    };
    fs[1] = {0, 0};
    tmp.push(1);
    sol(ds, fs);
    assert(fs[n].first != -1);
  
    vector<int> path;
    vector<bool> V(n+1);
    map<int,int> onpath, pos;
    int cnt=0;
    for(int i=n; i!=1; i=fs[i].first)
        ft[fs[i].first]={i, fs[i].second}, tmp.push(i), V[i]=1, path.push_back(fs[i].second);
    V[1]=1;
    tmp.push(1); ft[n]={0, 0};
    sol(dt, ft);
    pos[1]=0;
    assert(ft[1].first != -1);
    for(int i=1; i!=n; i=ft[i].first) pos[ft[i].first]=++cnt;
  
    reverse(all(path));
    for(int i=0;i<path.size();++i) onpath[path[i]]=i;
  
    vector upd(cnt+2, vector<pair<int,ll>>());
    vector<ll> ans(path.size());
    vector<int> lcas(n+1, -1), lcat(n+1, -1);
  
    auto getlca = [&](auto& lca, auto& fa)
    {
        vector G(n+1, vector<int>());
        int rt;
        for(int i=1;i<=n;++i) if(fa[i].first!=0) {if(fa[i].first!=-1) G[fa[i].first].push_back(i);} 
                              else rt=i;
      
        function<void(int,int)> dfs=[&](int x, int tp)
        {
            if(V[x]) tp=x; lca[x]=tp;
            for(auto y : G[x]) dfs(y, tp);
        };
      
        dfs(rt, rt);
    };
  
    getlca(lcas, fs); getlca(lcat, ft);
    pos[-1]=-1;
  
    for(int i=0;i<m;++i)
    {
        auto [x, y, w] = e[i];
        if(!onpath.count(i) && ds[x]!=1e18 && dt[y]!=1e18)
        {
            ll d=ds[x]+dt[y]+w;
            int posx=pos[lcas[x]], posy=pos[lcat[y]];
            assert(posx!=-1&&posy!=-1);
            if(posy>posx) upd[posx].push_back({posy, d});
          
            d=dt[x]+ds[y]+w;
            posx=pos[lcas[y]], posy=pos[lcat[x]];
            assert(posx!=-1&&posy!=-1);
            if(posy>posx) upd[posx].push_back({posy, d});
        }
    }
  
    struct bit
    {
        vector<ll> t; int siz;
        bit(int siz) : siz(siz+1), t(siz+3, 1e18) {}
        void C(int x, ll y)
        {
            for(;x;x-=(x&-x)) cmin(t[x], y);  
        }
        ll G(int x)
        {
            ll ret=1e18;
            for(;x<=siz;x+=(x&-x)) cmin(ret, t[x]);
            if(ret==1e18) return -1;
            return ret;
        }
    };
  
    bit B(cnt);
    for(int i=0;i<path.size();++i)
    {
        for(auto [r, d] : upd[i]) assert(r<=cnt&&r>i), B.C(r, d);
        ans[i]=B.G(i+1);
    }
  
    for(auto x : que)
    {
        auto [X, y, z] = e[x-1];
        if(onpath.count(x-1)) cout << ans[onpath.at(x-1)] << "\n";
        else cout << ds[n] << "\n";
    }
    return 0;
}