当前位置: 代码迷 >> 综合 >> [Codeforces938D][Dijkstra]Buy a Ticket
  详细解决方案

[Codeforces938D][Dijkstra]Buy a Ticket

热度:92   发布时间:2023-12-19 05:36:14.0

翻译:

给定一张包含n(n<=2*10^5)个节点的图,给出m(m<=2*10^5)条双向边,边有权,每个点也有权
对于每个点i,你要输出i到任意一个点再回来的最小代价,到达那个点时要加入那个点的点权,经过则不用

题解

可以发现,假如不计边权的情况下,一个点到另一个点的来回路径是固定的。即为这个点到那个点的最短路。在这个条件下,我们直接把边权全部*2,一个点到另一个点的最短路为这个点到那个点的最短往返路径
新建一个节点ed,每个点向ed连一条边,边权为这个点的点权。
问题便转化为,求任意一个点i到ed的最短距离
反向建图跑最短路,再次转化为ed到每个点i的最短距离
边的数量很大而点数量不大,这题是卡SPFA的,所以写一个Dijkstra代替

/* 翻译: 给定一张包含n(n<=2*10^5)个节点的图,给出m(m<=2*10^5)条双向边,边有权,每个点也有权 对于每个点i,你要输出i到任意一个点再回来的最小代价,到达那个点时要加入那个点的点权,经过则不用 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
LL d[210000];
struct pt
{int x;friend bool operator <(pt n1,pt n2){
   return d[n1.x]>d[n2.x];}
};
priority_queue<pt> q;
inline LL read()
{LL f=1,x=0;char ch=getchar();while(ch<'0' || ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
struct node
{LL c;int x,y,next;
}a[810000];int len,last[210000];
void ins(int x,int y,LL c)
{len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;
}
int n,m,st;
bool v[210000];
int main()
{n=read();m=read();st=n+1;len=0;memset(last,0,sizeof(last));for(int i=1;i<=m;i++){int x=read(),y=read();LL c=read();ins(x,y,2*c);ins(y,x,2*c);}for(int i=1;i<=n;i++){LL x=read();ins(st,i,x);}memset(d,63,sizeof(d));d[st]=0;memset(v,false,sizeof(v));v[st]=true;pt tmp;tmp.x=st;q.push(tmp);while(!q.empty()){tmp=q.top();int x=tmp.x;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(d[y]>d[x]+a[k].c){d[y]=d[x]+a[k].c;if(v[y]==false){v[y]=true;pt cnt;cnt.x=y;q.push(cnt);}}}q.pop();v[x]=false;}for(int i=1;i<n;i++)printf("%lld ",d[i]);printf("%lld\n",d[n]);return 0;
}
  相关解决方案