正題

---

題目大意

$n$個點$m$條邊的無向圖，每個點有門票費，對于每個點求一個點使得去那里看完賽艇并回來消耗的時間最小。

---

解題思路

因為是無向圖，所以去和回是同一條路，把每個點作為起點將門票費壓入然后跑最短路。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const ll N=2e5+10; struct node{ll x,w; }; struct edge_node{ll to,next,w; }a[N*2]; ll n,m,f[N],ls[N],tot; bool v[N]; priority_queue<node> q; bool operator<(node x,node y) {return x.w>y.w;} void addl(ll x,ll y,ll w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w; } void dij() {while(!q.empty()){ll x=q.top().x;q.pop();if(v[x]) continue;v[x]=1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;if(!v[y])q.push((node){y,f[y]});}}} } int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=m;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);addl(x,y,w*2);addl(y,x,w*2);}for(ll i=1;i<=n;i++){scanf("%lld",&f[i]);q.push((node){i,f[i]});}dij();for(ll i=1;i<=n;i++)printf("%lld ",f[i]); }

總結(jié)

以上是生活随笔為你收集整理的nssl1436-赛艇表演【最短路】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。