【比赛链接】
【题解】
Problem A Word Correction【字符串】
不用多说了吧，字符串的基本操作
Problem B Run for your prize【贪心】
我们可以将这个数轴一分为二，小于等于500000的由第一个人领，否则由第二个人领
Problem C Constructing tests【贪心】【数学】
首先我们发现 ： N^2 - (N / M)^2 = x （N/M向下取整）
然后我们算出N的上下界，发现： sqrt(x+1)<=N<=sqrt(3/4*x) (sqrt是开根号的意思）
所以我们可以枚举N，算出M
Problem D Buy a ticket【最短路】
首先想到可以跑N遍最短路
但是很显然，这样会超时，那么我们该如何优化呢？
我们不妨先建一个原点，将原点与每个城市连边，权值为在这个城市开演唱会的价格ai，然后再将城市与城市之间连边，
但是每条路径上的权值要乘2，因为是往返的费用
我们发现，只要对这个图跑一遍最短路，就得出了答案。
注意N最大10^5，SPFA不能过，要用dijkstra+堆优化
代码 ：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = * 1e5; LL i,N,M;
LL dist[MAXN+],a[MAXN+],b[MAXN+],c[MAXN+],w[MAXN+],vis[MAXN+];
vector< pair<LL,LL> > E[MAXN+]; template <typename T> inline void read(T &x) {
LL f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = x * + c - '';
x *= f;
} template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
} template <typename T> inline void writeln(T x) {
write(x);
puts("");
} inline void dijkstra(LL st) {
LL i,x,to,cost;
priority_queue< pair<LL,LL> > q;
for (i = ; i <= N; i++) dist[i] = LONG_LONG_MAX;
q.push(make_pair(,st));
dist[st] = ;
memset(vis,,sizeof(vis));
while (!q.empty()) {
x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = ;
for (i = ; i < E[x].size(); i++) {
to = E[x][i].first;
cost = E[x][i].second;
if (dist[x] + cost < dist[to]) {
dist[to] = dist[x] + cost;
q.push(make_pair(-dist[to],to));
}
}
}
} int main() { read(N); read(M);
for (i = ; i <= M; i++) {
read(a[i]); read(b[i]); read(w[i]);
E[a[i]].push_back(make_pair(b[i],w[i]*));
E[b[i]].push_back(make_pair(a[i],w[i]*));
}
for (i = ; i <= N; i++) {
read(c[i]);
E[N+].push_back(make_pair(i,c[i]));
}
dijkstra(N+);
for (i = ; i <= N; i++) {
if (i == ) write(dist[i]);
else { putchar(' '); write(dist[i]); }
}
puts(""); return ;
}