B. 看比赛 The 10th Jimei University Programming Contest

Problem - B - Codeforces

题目大意：有一个n的个点的无向边权图，A和B两个人要从1号点去往n号点，每一轮，他们会轮流选择下一步要走的一条边，然后两个人一起走过去，A先选，他们每次选的路一定是到1到n的最短路上的一条边，最后到n时轮到谁选就算谁输，问谁能赢

2<=n<=1e5；2<=m<=2e5;1<=w[i]<=1e9

思路：因为直走最短路，所以我们把所有在最短路上的边都要选出来，建成新图，为此，首先用dijkstra求出1到n的最短路的长度，然后我们从n开始bfs，遍历相邻边，如果这条边的边权加上1到这条边起点的最短路距离等于1到这条边终点的最短路距离，那么就把这条边加到新图中，最后就会形成一个包含1到n的所有最短路的DAG。

        然后考虑sg的转移，显然当他们在n点时，先手必败，令sg[n]=0，然后因为新图是无向图，所以按照常规树上博弈的方法转移，sg[u]=MEX(sg[v1],sg[v2]...)，但因为不是树而是图，所以要记忆化一下，避免重复遍历

#include
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 10, M = 2e5 + 10;
const ll INF = 1e18;
struct Edge
{
	int u, v, next;
	ll w;
}e[M*2];//链式前向星存图
struct node
{//优先队列中存储的点的编号和最短路
	int id;
	ll dis;
	bool operator<(const node& a)const
	{
		return dis > a.dis;
	}//因为我们要小的先出队，所以要把小于号重载为大于
	node(int a, ll b)
	{
		id = a, dis = b;
	}
};
int head[N], cnt = 0;
void addedge(int u, int v, ll w)
{//这里边的起点也要记录
	e[++cnt].v = v;
	e[cnt].u = u;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}
int n, m;
ll dis[N];
bool done[N];
ll fid;
ll sg[N];
set<int>ins;
vector<int>g[N];
bool vis[N];
void bfs()
{//建立新图
	queue<int>q;
	q.push(n);//从n开始bfs
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;//避免重复遍历
		for (int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].v;
			ll w = e[i].w;
			if (dis[v] + w == dis[u])
			{//这个边是想要的边
				g[v].push_back(u);
				q.push(v);				
			}
		}
	}
}
void dijkstra()
{
	int s = 1;
	for (int i = 1; i <= n; i++)
	{
		dis[i] = INF;//初始化到所有点的最短路为一极大值
		done[i] = 0;//判断每个点是否在集合A里
	}
	dis[s] = 0;
	priority_queueq;
	q.push(node(s, dis[s]));
	while (!q.empty())
	{
		node u = q.top();
		q.pop();
		if (done[u.id])
		{//已在集合A中的点说明已经找到最短路了
			continue;
		}
		done[u.id] = 1;
		for (int i = head[u.id]; ~i; i = e[i].next)
		{
			int v = e[i].v;
			ll w = e[i].w;
			if (done[v])
			{
				continue;
			}//避免回头访问到处理过的点
			if (dis[v] > w + u.dis)
			{
				dis[v] = w + u.dis;//维护最短路
				q.push(node(v, dis[v]));
			}
		}
 
	}
}
int dfs2(int u)
{//求sg
	if (sg[u] != -1)
	{//记忆化
		return sg[u];
	}
	set<int>temp;
	for (int i = 0; i < g[u].size(); i++)
	{// 遍历子节点
		int v = g[u][i];
		temp.insert(dfs2(v));
	}
	int now = 0;
	for (set<int>::iterator it = temp.begin(); it != temp.end(); it++)
	{//找MEX
		if (*it == now)
		{
			now++;
		}
		else
		{
			sg[u] = now;
			return sg[u];;
		}
	}
	sg[u] = now;
	return sg[u];
}
void init()
{
	cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		head[i] = -1;
		g[i].clear();
		sg[i] = -1;
		vis[i] = 0;
	}
	ins.clear();
}
void solve()
{
	cin >> n;
	init();
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		ll u, v, w;
		cin >> u >> v >> w;
		addedge(u, v, w);
		addedge(v, u, w);
	}
	dijkstra();
	fid = dis[n];
	bfs();
	sg[n] = 0;
	dfs2(1);
	if (!sg[1])
	{//sg=0这里表示先手必输
		cout << "Little I is the winner.\n";
		return;
	}
	cout << "Little M is the winner.\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	//t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}
 //6 7
 //1 2 1
 //2 3 1
 //2 4 2
 //3 4 1
 //4 5 1
 //5 6 1
 //4 6 2
 //2 1
 //1 2 1
 //3 3
 //1 2 1
 //2 3 1
 //1 3 3
 //8 9
 //1 2 1
 //2 3 1
 //2 4 2
 //3 4 1
 //4 5 1
 //5 8 1
 //4 8 2
 //1 7 2
 //1 6 1