CF360E Levko and Game（贪心）

这题贪心停水的，找\(dis1<=dis2\)的点往歇斯底里地砍，砍到没法砍就是。

写博客是为了记录下遇到的神奇bug

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define ON_DEBUGG

#ifdef ON_DEBUGG

#define D_e_Line printf("\n-----------\n")

#define D_e(x) std::cout << (#x) << " : " <<x << "\n"

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out.txt", "w", stdout)

#define Pause() system("pause")

#include <ctime>

#define TIME() fprintf(stderr, "\nTIME :　%.3lfms\n", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;

#define D_e(x) ;

#define FileOpen() ;

#define FilSave ;

#define Pause() ;

#define TIME() ;

#endif

struct ios {

	template<typename ATP> ios& operator >> (ATP &x) {

		x = 0; int f = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;

		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

		x *= f;

		return *this;

	}

}io;

using namespace std;

template<typename ATP> inline ATP Min(ATP a, ATP b) {

	return a < b ? a : b;

}

template<typename ATP> inline ATP Max(ATP a, ATP b) {

	return a > b ? a : b;

}

#include <queue>

const int N = 100007;

const int M = 1000007;

#define int long long

struct Edge {

	int nxt, pre, from, w;

} e[M];

int head[N], cntEdge;

inline void add(int u, int v, int w) {

	e[++cntEdge] = (Edge){ head[u], v, u, w}, head[u] = cntEdge;

}

struct nod {

	int x, w;

	bool operator < (const nod &com) const {

		return w > com.w;

	}

};

priority_queue<nod> q;

int dis1[N], dis2[N];

int n, m, K, S1, S2, T;

inline void Dijkstra(int st, int *dis) {

//	Fill(dis, 0x3f); This sentence lead to a bug

/*

[Warning] argument to 'sizeof' in 'void* memset(void*, int, size_t)' call is

the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]

*/

	R(i,0,n) dis[i] = 0x7fffffff;

	dis[st] = 0;

	q.push((nod){ st, 0});

	while(!q.empty()){

		int u = q.top().x, w = q.top().w;

		q.pop();

		if(w != dis[u]) continue;

		for(register int i = head[u]; i; i = e[i].nxt){

			int v = e[i].pre;

			if(dis[v] > dis[u] + e[i].w){

				dis[v] = dis[u] + e[i].w;

				q.push((nod){ v, dis[v]});

			}

		}

	}

}

int l[N], r[N], pos[N];

#undef int

int main() {

#define int long long

	io >> n >> m >> K >> S1 >> S2 >> T;

	R(i,1,m){

		int u, v, w;

		io >> u >> v >> w;

		add(u, v, w);

	}

	R(i,1,K){

		int u, v;

		io >> u >> v;

		io >> l[i] >> r[i];

		add(u, v, r[i]);

		pos[i] = cntEdge;

	}

	while(1){

		int flag = false;

		Dijkstra(S1, dis1);

		Dijkstra(S2, dis2);

		R(i,1,K){

			int v = e[pos[i]].from;

			if((dis1[v] <= dis2[v]) && e[pos[i]].w != l[i]){

				e[pos[i]].w = l[i];

				flag = true;

			}

		}

		if(flag == false) break;

	}

	if(dis1[T] < dis2[T]) printf("WIN\n");

	else if(dis1[T] == dis2[T]) printf("DRAW\n");

	else{

		printf("LOSE\n");

		return 0;

	}

	R(i,1,K){

		printf("%lld ", e[pos[i]].w);

	}

	return 0;

}

cdecl：

sizeof 一个指针肯定会死啊

这样只会 memset 前 4（64 位机的话，8）个 bit

CF360E Levko and Game（贪心）的相关教程结束。