CF 360E Levko and Game——贪心

时间：2020-12-29 05:16:39

题目：http://codeforces.com/contest/360/problem/E

官方题解与证明：http://codeforces.com/blog/entry/9529

一条可以调整的边的边权要么是 l [ i ] 要么是 r[ i ] 。

先把所有可调整边设成 r[ i ] ，然后看看有没有一条可调整的边 (x,y)满足 dis1[x]<=dis2[x] 且其边权还是 r[ i ]；如果有，就把它改成 l [ i ]。

改完一条边之后就再做一遍 dij( ) ，然后再改；直到没有可改的边。

其实每次可以不止改一条边，可以把能改的边都改了。因为据证明，一条边 (x,y) 如果 dis1[x]<=dis2[x] ，不会在之后某次修改别的边的时候变成 dis1[x]>dis2[x] 了；所以一旦能改，就一直能改，所以一次改很多能改的边也是可以的。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

using namespace std;

const int N=1e4+,M=;

int n,m,t,hd[N],xnt,bh[M],l[M],r[M],s1,s2,F;

ll dis1[N],dis2[N];bool vis[N],ans[M];

priority_queue<pair<ll,int> > q;

struct Ed{

  int x,to,nxt,w;

  Ed(int f=,int a=,int b=,int c=):x(f),to(a),nxt(b),w(c) {}

}ed[N+M];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void add(int x,int y,int z){ed[++xnt]=Ed(x,y,hd[x],z);hd[x]=xnt;}

void dj()

{

  memset(dis1,0x3f,sizeof dis1);dis1[s1]=;

  memset(vis,,sizeof vis);

  q.push(make_pair(,s1));

  while(q.size())

    {

      int k=q.top().second;q.pop();

      if(vis[k])continue;vis[k]=;

      for(int i=hd[k],v;i;i=ed[i].nxt)

    if(dis1[v=ed[i].to]>dis1[k]+ed[i].w)

      dis1[v]=dis1[k]+ed[i].w,q.push(make_pair(-dis1[v],v));

    }

  memset(dis2,0x3f,sizeof dis2);dis2[s2]=;

  memset(vis,,sizeof vis);

  q.push(make_pair(,s2));

  while(q.size())

    {

      int k=q.top().second;q.pop();

      if(vis[k])continue;vis[k]=;

      for(int i=hd[k],v;i;i=ed[i].nxt)

    if(dis2[v=ed[i].to]>dis2[k]+ed[i].w)

      dis2[v]=dis2[k]+ed[i].w,q.push(make_pair(-dis2[v],v));

    }

}

int main()

{

  n=rdn();m=rdn();t=rdn();

  s1=rdn();s2=rdn();F=rdn();

  for(int i=,u,v,z;i<=m;i++)

    u=rdn(),v=rdn(),z=rdn(),add(u,v,z);

  for(int i=,u,v;i<=t;i++)

    {

      u=rdn();v=rdn();l[i]=rdn();r[i]=rdn();

      add(u,v,r[i]); bh[i]=xnt;

    }

  bool flag;

  while()

    {

      dj();flag=;

      for(int i=,d;i<=t;i++)

    {

      d=bh[i];

      if(ed[d].w==l[i]||dis1[ed[d].x]>dis2[ed[d].x])continue;

      ed[d].w=l[i];ans[i]=;flag=;

    }

      if(!flag)break;

    }

  dj();

  if(dis1[F]>dis2[F]){puts("LOSE");return ;}

  if(dis1[F]==dis2[F])puts("DRAW"); else puts("WIN");

  for(int i=;i<=t;i++)printf("%d ",ans[i]?l[i]:r[i]);puts("");

  return ;

}

相关文章