最短路拓展

0X01 分层图最短路

题目
我们可以把这种有 \(k\) 次把 \((u,v)\) 改变成 \(w\) 题目叫做 分层图最短路
你还记得 Dijkstra 吗 对!我们可以仿照 Dijkstra 的思路 从起点 \(s\) 开始跑一遍最短路然后返回 \(l_t\)
但有个问题来了 我们有 \(k\) 次改变边权的机会啊
那我们是不是可以把改变了 \(a\) 次后的图存下来在和改变 \(a-1\) 后的图拼接起来呢
没错 这就是分层图最短路 可能单说理解不了 那看 code
code:
[code]//LG//[JLOI2011] 飞行路线//https://www.luogu.com.cn/problem/P4568#includeusing namespace std;using ll=long long;struct e{        int u,v;        int w;};vector G[110010];int n,m,k,s,t;int Dijkstra(int s,int t){        vector l(n*(k+1)+10,INT_MAX);l=0;        vector f(n*(k+1)+10,1);        priority_queue q;        q.push(make_pair(0,s));        while(q.size()){                int u=q.top().second;q.pop();                if(f){                        f=0;                        for(int j=0;jl+w){                                        l[v]=l+w;                                        q.push(make_pair(-l[v],v));                                }                        }                }        }        int ans=INT_MAX;        for(int i=0;i>n>>m>>k;    cin>>s>>t;        while(m--){                int u,v,w;                cin>>u>>v>>w;                for(int i=0;i>s>>t;        while(m--){                int u,v,w;                cin>>u>>v>>w;                G.push_back({u,v,w});                G[v].push_back({v,u,w});        }        cout>T;    while(T--){        cin>>n>>m;        for(int i=1;i>u>>v>>w;            if(w>=0){                G.push_back({u,v,w});                        G[v].push_back({v,u,w});            }else{                G.push_back({u,v,w});            }            }            cout

很好很强大  我过来先占个楼 待编辑