对拍（多线程+计算运行时间）
例题：https://www.luogu.com.cn/problem/U549198
利用
操作方法可以把
Compare.cpp
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include<windows.h>
#include<time.h>
#include<thread>
using namespace std;
#define timer std::chrono::_V2::system_clock::time_point
class Timers
{
public:
timer start = chrono::high_resolution_clock::now();
void Start()
{
start = chrono::high_resolution_clock::now();
}
//1s数据：hzoi:1450；Luogu:978
unsigned long long GetEnd()
{
timer stop = chrono::high_resolution_clock::now();
unsigned long long spend = chrono::duration_cast<std::chrono::milliseconds>(stop - start).count();
return spend;
}
} Timer;
signed main()
{
long long cnt = 0;
while (1)
{
system("MakeData.exe"); //造数据
Timer.Start();
thread t1(system, "ProgramA.exe"), t2(system, "ProgramB.exe");
t1.join(), t2.join(); //多线程拍
system("cls"); //清屏
time_t timep;
time(&timep);
cout << "Thread: " << ++cnt << "\nTramp: " << ctime(&timep);
cout << "Runtime: " << Timer.GetEnd() << "ms \n\n";
if (system("fc ProgramA.out ProgramB.out"))
{
system("start Data.in");
exit(0);
}
}
return 0;
}MakeData.cpp
#include<bits/stdc++.h>
using namespace std;
class Quick_IO
{
public:
template<typename T>
void write(T x)
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
} io;
mt19937 Rand(time(0)); //默认int类型随机数
int RandNum(int Min, int Max)
{
int x = Min + Rand() % (Max - Min + 1);
return x;
}
signed main()
{
freopen("Data.in", "w+", stdout);
int n = RandNum(39800, 40000), m = RandNum(999990, 1000000), k = RandNum(999990, 1000000);
io.write(n), putchar(' ');
io.write(m), putchar(' ');
io.write(k), putchar('\n');
for (int i = 1; i <= m; i++)
{
int a = RandNum(1, n);
int b = RandNum(1, n);
while (a == b) b = RandNum(1, n);
io.write(a), putchar(' ');
io.write(b), putchar(' ');
io.write(RandNum(1, 210000000)), putchar('\n');
}
for (int i = 1; i <= k; i++)
{
int a = RandNum(1, n);
int b = RandNum(1, n);
while (a == b) b = RandNum(1, n);
io.write(a), putchar(' ');
io.write(b), putchar(' ');
io.write(RandNum(1, 210000000)), putchar('\n');
}
}ProgramA.cpp
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <map>
#include <algorithm>
using namespace std;
struct Edge
{
int v;
int w;
// 不再使用 collapse 字段，特殊桥梁信息将存储在 specialMap 中
};
const int INF = 0x3f3f3f3f;
// 辅助函数：生成无向边 key（保证 u<=v）
inline long long encode(int u, int v)
{
if (u > v)
swap(u, v);
return ((long long)u << 32) | v;
}
int main()
{
freopen("Data.in", "r", stdin);
freopen("ProgramA.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<vector<Edge>> graph(n + 1);
// 先读 m 条铁路
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
// 无向图，添加双向边
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
// 使用 map 存储特殊桥梁信息，key 为无向边编码，value 为断裂时间
map<long long, int> specialMap;
for (int i = 0; i < k; i++)
{
int u, v, t;
cin >> u >> v >> t;
long long key = encode(u, v);
auto it = specialMap.find(key);
// 若存在多次输入同一特殊边，只更新为更小的断裂时间
if (it == specialMap.end())
specialMap.emplace(key, t);
else if (t < it->second)
it->second = t;
}
vector<int> dist(n + 1, INF);
dist[1] = 0;
// (当前时间, 节点)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 1});
while (!pq.empty())
{
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u])
continue;
for (auto &edge : graph[u])
{
long long key = encode(u, edge.v);
auto it = specialMap.find(key);
// 若找到特殊桥梁限制，则检查是否允许通过
if (it != specialMap.end() && d + edge.w > it->second)
continue;
if (d + edge.w < dist[edge.v])
{
dist[edge.v] = d + edge.w;
pq.push({dist[edge.v], edge.v});
}
}
}
cout << (dist[n] == INF ? -1 : dist[n]) << "\n";
return 0;
}ProgramB.cpp
/*
注意更新的逻辑！
即使这个点不能再入队，也要更新答案
*/
#include<bits/stdc++.h>
#define N 40005
#define M 1000005
#define int long long
using namespace std;
class Quick_IO
{
public:
template<typename T>
void read(T &r)
{
T x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
r = x*f;
}
template<typename T, typename... Args>
void read(T &tmp, Args &... tmps)
{
read(tmp);
read(tmps...);
}
template<typename T>
void write(T x)
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
} io;
int n, m, k;
struct node1
{
int v, t, lim;
};
vector<node1> G[N];
struct node2
{
int u, v, t;
} Ques[M];
map<pair<int, int>, int> Ck;
struct node
{
int u, w;
friend bool operator < (node a, node b)
{
return a.w > b.w;
}
};
#define inf 0x3f3f3f3f
int dis[N], vis[N];
priority_queue<node> q;
void Dijk()
{
for (int i = 1; i <= n; i++) dis[i] = inf;
dis[1] = 0;
q.push({1, 0});
while (!q.empty())
{
int u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = 0; i < G[u].size(); i++)
{
node1 aim = G[u][i];
if (dis[aim.v] > dis[u] + aim.t && (dis[u] + aim.t <= aim.lim || aim.lim == 0))
{
dis[aim.v] = dis[u] + aim.t;
q.push({aim.v, dis[aim.v]});
}
}
}
}
signed main()
{
freopen("Data.in", "r", stdin);
freopen("ProgramB.out", "w", stdout);
io.read(n, m, k);
for (int i = 1; i <= m; i++) io.read(Ques[i].u, Ques[i].v, Ques[i].t);
for (int i = 1; i <= k; i++)
{
int u, v, t;
io.read(u, v, t);
if (u > v) swap(u, v);
Ck[ {u, v}] = t;
}
for (int i = 1; i <= m; i++)
{
if (Ques[i].u > Ques[i].v) swap(Ques[i].u, Ques[i].v);
int u = Ques[i].u, v = Ques[i].v, w = Ques[i].t;
G[u].push_back({v, w, Ck[{u, v}]});
G[v].push_back({u, w, Ck[{u, v}]});
}
Dijk();
if (dis[n] >= inf) io.write(-1);
else io.write(dis[n]);
}