网站设计网站机构,龙岗商城网站建设最好,wordpress 数据库崩溃,wordpress引流插件E - Minimum Path
分层图最短路 第一个分层图 第0层就是按照题中给的点连边#xff0c;从第0层到第1层我们连一条边权是0的边#xff0c;从第1层到第2层连一条边权是原先边权2倍的边#xff0c;当然第1层以及第2层之间按照原图连边。 第二个分层图 第0层就是按照题中给的点…E - Minimum Path
分层图最短路 第一个分层图 第0层就是按照题中给的点连边从第0层到第1层我们连一条边权是0的边从第1层到第2层连一条边权是原先边权2倍的边当然第1层以及第2层之间按照原图连边。 第二个分层图 第0层就是按照题中给的点连边从第0层到第1层我们连一条边权是原先边权2倍的边从第1层到第2层连一条边权0的边当然第1层以及第2层之间按照原图连边。
然后最终答案在两个分层图的第二层比较。如果从1到某个点只存在一条边那么最短路应该与第0层的答案相同再顺便比较一下即可。
为什么有两个分层图 第一个分层图我们从0—1层花费是0代表少经过一条边从1—2层花费原先两倍边权两者结合代表用一条边的边权代替另一题边的边权。而这样建图表示最长边出现在最短边之前。 而第二个分层图代表最短边出现最长边之前。而所有点的最短路无非这两种情况。
对于一条路径我们没考虑减去最大值加上最小值而是用一条路边替另一条边而最短路径一定是最小的边代替最长的边
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includebitset
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairll,int pli;
const int N600010;
const int M4000010;
int h1[N],h2[N],e[M],ne[M],idx;
int n,m;
ll w[M],d1[N],d2[N];
bool st[N];
void add(int h[],int a,int b,ll c)
{e[idx]b;w[idx]c;ne[idx]h[a];h[a]idx;
}
void dijkstra(int h[],ll dist[])
{//memset(dist,0x3f,8*N);memset(st,0,sizeof st);dist[1]0;priority_queuepli,vectorpli,greaterpli q;q.push({0,1});while(q.size()){ll dq.top().first,tq.top().second;q.pop();if(st[t]) continue;st[t]1;for(int ih[t];i!-1;ine[i]){int je[i];if(dist[j]dw[i]) {dist[j]dw[i];q.push({dist[j],j});}}}
}int main()
{IO;int T1;//cinT;while(T--){cinnm;memset(h1,-1,sizeof h1);memset(h2,-1,sizeof h2);memset(d1,0x3f,sizeof d1);memset(d2,0x3f,sizeof d2);while(m--){int a,b,c;cinabc;add(h1,a,b,c),add(h1,b,a,c);add(h1,an,bn,c),add(h1,bn,an,c);add(h1,a2*n,b2*n,c),add(h1,b2*n,a2*n,c);add(h1,a,bn,0);add(h1,b,an,0);add(h1,an,b2*n,2*c);add(h1,bn,a2*n,2*c);add(h2,a,b,c),add(h2,b,a,c);add(h2,an,bn,c),add(h2,bn,an,c);add(h2,a2*n,b2*n,c),add(h2,b2*n,a2*n,c);add(h2,a,bn,2*c);add(h2,b,an,2*c);add(h2,an,b2*n,0);add(h2,bn,a2*n,0);}dijkstra(h1,d1);dijkstra(h2,d2);for(int i2;in;i)coutmin(min(d1[i],d1[i2*n]),d2[i2*n]) ;cout\n;}return 0;
}可惜和队友想出做法的时候就剩10分钟了没能完成可惜可惜
