题目: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 ;
}

最新文章

  1. WebService -- Java 实现之 CXF ( 使用CXF工具生成client 程序)
  2. NYOJ-取石子(二)
  3. WCF 回调中操作线程
  4. Android三种基本的加载网络图片方式(转)
  5. GitHub 里面有大量优秀的第三方框架
  6. phpstorm安装,破解及使用
  7. mongodb在window下和linux下的部署 和 安装可视化工具
  8. Photoshop CS6 基础知识
  9. kiss框架学习
  10. ZOJ2105 终于找到错误
  11. intellij idea on update action\on frame deactivation ||Servlet 页面不同步问题
  12. [USACO14DEC]驮运Piggy Back
  13. C#模板设计模式使用和学习心得
  14. 环境部署(三):Linux下安装Git
  15. vue搭建脚手架
  16. 【Codeforces 86C】Genetic engineering
  17. PHP中的字符串 — 表示方法
  18. git commit -m 与 git commit -am的区别
  19. SQL中查询前几条或者中间某几行数据limit
  20. ImageView中scaleType属性详解

热门文章

  1. Java集合详解8:Java的集合类细节精讲
  2. mysql中一个字段根据另一字段的值分割为不同列
  3. qml自定义带文字的button tabbutton
  4. PHP exec()函数的介绍和使用DEMO
  5. xss 防御
  6. Linux:Aircrack-ng
  7. javaScript高程笔记--最佳实践
  8. Python报错IOError: [Errno 22] invalid mode ('r') or filename
  9. python常用模块之shelve模块
  10. c# mysql and sqlserver数据库连接字符串