CF1486E Paired Payment
题目描述
给你 n(n≤1e5) 个点 m(m≤2e5) 条双向边,每条边的权值为[1,50]
但是一次至少走两步,权值为两个边边权和的平方。求 1 到其他每个点的最短距离
Solution
注意 Dijkstra 的性质,先到达的并且在优先队列最前的一定是当前能向外跑的最短的。
我们设当前应更新 x \to y \to z
如果当前 x \to y 是 所有点 \to y 的较短的,就可以用它去更新x\to y \to z
而接下来如果遇到一个点 w ,有 w \to y 和 x\to y 相等,那么此时 w \to y 已经不能更新 y\to z 了
因为Dijkstra 的性质,注定有 dis[x]<dis[w]
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e5+10;
int dis[N],v[N],dp[N][51],m,n;
int mn[N];
vector<pair<int,int>> vec[N];
void init(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
vec[x].push_back(make_pair(y,w));
vec[y].push_back(make_pair(x,w));
}
}
void solve(){
priority_queue<pair<int,int> > q;
memset(dis,0x3f,sizeof(dis));
memset(mn,0x3f,sizeof(mn));
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty()){
pair<int,int> now = q.top(); q.pop();
int x = now.second;
if(v[x]) continue;
v[x]=1;
//printf("%d\n",x);
for(auto p:vec[x]){
int y = p.fi;
if(p.se>=mn[y]) continue;
mn[y]=p.se;
for(auto r:vec[y]){
int t_ = r.fi;
if(v[t_]) continue;
if(dis[t_]>dis[x]+(p.se+r.se)*(p.se+r.se)){
dis[t_]=dis[x]+(p.se+r.se)*(p.se+r.se);
q.push(make_pair(-dis[t_],t_));
}
}
}
}
for(int i=1;i<=n;++i)
if(dis[i]>=0x3f3f3f3f) printf("-1 ");
else printf("%d ",dis[i]);
}
int main(){
init();
solve();
return 0;
}
0 条评论