C++(clang++ 11.0.1) 解法, 执行用时: 173ms, 内存消耗: 18732K, 提交时间: 2022-09-24 16:28:22

#include <bits/stdc++.h>
using namespace std;
const int N=3005,M=2e6+5;
int n,m,d[N],hd[N],V[M],nx[M],W[M],t,vis[N],in[N];
queue<int>q;
void add(int u,int v,int w){
//     cout<<u<<" "<<v<<" "<<w<<endl;
	nx[++t]=hd[u];V[hd[u]=t]=v;W[t]=w;
}
int main(){
	scanf("%d%d",&n,&m);
	if (n&1){
		puts("?");return 0;
	}
	for (int i=1,l,r,x;i<=m;i++){
		scanf("%d%d%d",&l,&r,&x);l--;
		if ((x+r-l)%2==1){
			puts("?");return 0;
		}
		x=(x+r-l)/2;
		if (x>r-l || x<0){
			puts("?");return 0;
		}
		add(l,r,x);
		add(r,l,-x);
	}
	for (int i=1;i<n;i++)
		add(i,0,-(i+1)/2);
    for (int i=1;i<=n;i++){
        add(i-1,i,1);
        add(i,i-1,0);
    }
	add(0,n,n/2);
	add(n,0,-n/2);
	for (int i=1;i<=n;i++) d[i]=1e9;
	q.push(0);vis[0]=1;in[0]++;
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
		if (d[0]<0){
			puts("?");return 0;
		}
		for (int i=hd[u];i;i=nx[i])
			if (d[V[i]]>d[u]+W[i]){
				d[V[i]]=d[u]+W[i];
				if (!vis[V[i]]){
					q.push(V[i]),
					vis[V[i]]=1,
					in[V[i]]++;
					if (in[V[i]]>n+1){
						puts("?");return 0;
					}
				}
			}
	}
	printf("! ");
	for (int i=1;i<=n;i++){
// 		d[i]=-d[i];
		if (d[i]==d[i-1]+1) putchar('(');
		else putchar(')');
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 1536ms, 内存消耗: 12464K, 提交时间: 2022-10-04 17:33:17

/* Author : flying_doraemon */
#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n, k, x, y, z;
	scanf("%d%d", &n, &k);

	vector<vector<pair<int, int>>> g(n + 1);

	vector<int> p(n + 2), dis(n + 1, 1 << 30), cnt(n + 1);
	dis[0] = 0;

	while (k--) {
		scanf("%d%d%d", &x, &y, &z);
		--x;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, -z);
	}

	for (int i = 1; i <= n; ++i) {
		g[i].emplace_back(0, 0);
		g[i].emplace_back(i - 1, 1);
		g[i - 1].emplace_back(i, 1);
	}
	g[0].emplace_back(n, 0);
	g[n].emplace_back(0, 0);

	vector<bool> vis(n + 1);

	queue<int> q;
	q.push(0);

	while (!q.empty()) {
		auto f = q.front();
		q.pop();
		vis[f] = 0;

		for (auto& [v, w] : g[f]) {
			if (dis[f] + w < dis[v]) {
				dis[v] = dis[f] + w;
				cnt[v] = cnt[f] + 1;
				if (!vis[v]) {
					if (cnt[v] > n) {
						puts("?");
						return;
					}
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}

	printf("! ");
	for (int i = 1; i <= n; ++i)
		if (dis[i] - dis[i - 1] == 1)
			printf("(");
		else
			printf(")");

	puts("");
}

int main(int argc, char** argv) {

	solve();

	return 0;
}