最短路拓展
0X01 分层图最短路题目
我们可以把这种有 \(k\) 次把 \((u,v)\) 改变成 \(w\) 题目叫做 分层图最短路
你还记得 Dijkstra 吗 对!我们可以仿照 Dijkstra 的思路 从起点 \(s\) 开始跑一遍最短路然后返回 \(l_t\)
但有个问题来了 我们有 \(k\) 次改变边权的机会啊
那我们是不是可以把改变了 \(a\) 次后的图存下来在和改变 \(a-1\) 后的图拼接起来呢
没错 这就是分层图最短路 可能单说理解不了 那看 code
code:
//LG// 飞行路线//https://www.luogu.com.cn/problem/P4568#includeusing namespace std;using ll=long long;struct e{ int u,v; int w;};vector G;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=l+w; q.push(make_pair(-l,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.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.push_back({v,u,w}); }else{ G.push_back({u,v,w}); } } cout 不错，里面软件多更新就更好了
页:
[1]