本文共 10432 字，大约阅读时间需要 34 分钟。

B题 Telephone Lines

中文题面：

分层图最短路

#include 
   
    using namespace std;#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)typedef long long ll; inline int read() {    int s = 0, w = 1; char ch = getchar();    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w;} const int N = 2e4 + 7; //节点数const int M = 2e4 + 7; //路径数const ll INF = 1e18;ll d1[N];//d1正向图，d2反向图struct Node {    int v;    ll cost;    bool operator < (Node b)const {        return cost > b.cost;    }};vector
    
      e[N];int n, m, k; void dijkstra(int s, ll d[], int p) {    priority_queue
     
        pq;    fill(d, d + N, INF);    d[s] = 0;    pq.push(Node{ s,0 });    while (!pq.empty()) {        Node    x = pq.top();        pq.pop();        if (d[x.v] < x.cost)    continue; //原先这个节点花费更少 跳过        for (auto it : e[x.v]) {            int z = it.cost > p;            if (d[it.v] > x.cost + z) {                d[it.v] = x.cost + z;                pq.push(Node{ it.v,d[it.v] });            }        }    }} int main() {    n = read(), m = read(), k = read();    for (int i = 1; i <= m; ++i) {        int u = read(), v = read(), w = read();        e[u].push_back(Node{ v, w });        e[v].push_back(Node{ u, w });    }    int l = 0, r = 1e9, ans = -1;    while (l <= r) {        int mid = l + r >> 1;        dijkstra(1, d1, mid);        if (d1[n] <= k)  ans = mid, r = mid - 1;        else   l = mid + 1;    }    printf("%d\n", ans);    return 0;}
     
    
   

dijkstra+dp

C题 最优贸易

#include
   
    using namespace std;#define sc(n) scanf("%c",&n)#define sd(n) scanf("%d",&n)#define pd(n) printf("%d\n", (n))#define sdd(n,m) scanf("%d %d",&n,&m)#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)#define pdd(n,m) printf("%d %d\n",n, m)#define ms(a,b) memset(a,b,sizeof(a))#define all(c) c.begin(),c.end()#define pb push_back #define fi first #define se second #define mod(x) ((x)%MOD)#define lowbit(x) (x & (-x))#define gcd(a,b) __gcd(a,b) typedef long long ll;typedef pair
    
      PII;typedef vector
     
       VI;typedef vector
      
        VS;const int MOD = 1e9 + 7;const double eps = 1e-9;const int inf = 0x3f3f3f3f;const int maxn = 100010; struct u {    int v, len;};int n, m, v[maxn], d[maxn * 3 + 1];vector
       G[maxn * 3 + 1]; void addEdge(int x, int y) {    G[x].push_back({ y,0 });    G[x + n].push_back({ y + n,0 });    G[x + 2 * n].push_back({ y + 2 * n,0 });    G[x].pb({ y + n,-v[x] });    G[x + n].pb({ y + 2 * n,v[x] });} queue
        
         q;bool inq[maxn * 3 + 1]; void spfa() { ms(d, -inf); d[1] = 0; inq[1] = true; q.push(1); while (q.size()) { int tp = q.front(); q.pop(); inq[tp] = false; int len = G[tp].size(); for (int i = 0; i < len; i++) { u x = G[tp][i]; if (d[x.v] < d[tp] + x.len) { d[x.v] = d[tp] + x.len; if (inq[x.v] == false) { q.push(x.v); inq[x.v] = true; } } } }} int main() { //freopen("in.txt","r",stdin); //调试用的 cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i]; for (int i = 1, x, y, z; i <= m; i++) { cin >> x >> y >> z; addEdge(x, y); if (z == 2) addEdge(y, x); } G[n].push_back( { 3 * n + 1, 0 }); G[n * 3].push_back( { 3 * n + 1, 0 });//超级终点是3*n+1编号 n = 3 * n + 1; //把n改成超级终点的编号，方便spfa操作 spfa(); cout << d[n] << endl; return 0;}
        
      
     
    
   

D题 Roads and Planes

#include
   
    using namespace std;#define N 25005#define M 200005struct Node{    int val, pos;    friend bool operator < (Node x, Node y) {        return x.val > y.val;    }};struct E { int next, to, dis; } e[M];int n, m1, m2, s, num, dfn;int h[N], bel[N], deg[N], dis[N];bool vis[N];vector
    
      c[N];queue
     
       que;int read(){    int x = 0, f = 1; char c = getchar();    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }    return x *= f;}void add(int u, int v, int w){    e[++num].next = h[u];    e[num].to = v;    e[num].dis = w;    h[u] = num;}void dfs(int x){    bel[x] = dfn, vis[x] = 1, c[dfn].push_back(x);    for (int i = h[x]; i != 0; i = e[i].next)        if (!vis[e[i].to]) dfs(e[i].to);}void dijkstra(int id){    priority_queue
      
        pue;    for (int i = 0; i < c[id].size(); i++) pue.push((Node) { dis[c[id][i]], c[id][i] });    while (pue.size())    {        int now = pue.top().pos;        pue.pop();        if (vis[now]) continue;        vis[now] = 1;        for (int i = h[now]; i != 0; i = e[i].next)        {            if (dis[now] + e[i].dis < dis[e[i].to])            {                dis[e[i].to] = dis[now] + e[i].dis;                if (bel[now] == bel[e[i].to]) pue.push((Node) { dis[e[i].to], e[i].to });            }            deg[bel[e[i].to]]--;            if (!deg[bel[e[i].to]] && bel[now] != bel[e[i].to]) que.push(bel[e[i].to]);        }    }}int main(){    cin >> n >> m1 >> m2 >> s;    for (int i = 1; i <= m1; i++)    {        int u = read(), v = read(), w = read();        add(u, v, w), add(v, u, w);    }    for (int i = 1; i <= n; i++)        if (!vis[i]) ++dfn, dfs(i);    for (int i = 1; i <= m2; i++)    {        int u = read(), v = read(), w = read();        add(u, v, w);        deg[bel[v]]++;    }    memset(vis, 0, sizeof(vis));    memset(dis, 0x3f, sizeof(dis));    dis[s] = 0, que.push(bel[s]);    for (int i = 1; i <= dfn; i++)        if (!deg[i]) que.push(i);    while (que.size())    {        int now = que.front();        que.pop();        dijkstra(now);    }    for (int i = 1; i <= n; i++)        if (dis[i] >= 1e9) printf("NO PATH\n");        else printf("%d\n", dis[i]);}
      
     
    
   

E题 Sorting It All Out

#include
   
    using namespace std;#define sc(n) scanf("%c",&n)#define sd(n) scanf("%d",&n)#define pd(n) printf("%d\n", (n))#define sdd(n,m) scanf("%d %d",&n,&m)#define sdcd(n,c,m) scanf("%d%c%d",&n,&c,&m)#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)#define pdd(n,m) printf("%d %d\n",n, m)#define ms(a,b) memset(a,b,sizeof(a))#define mod(x) ((x)%MOD)#define lowbit(x) (x & (-x)) typedef long long ll;typedef pair
    
      PII;typedef vector
     
       VI;typedef vector
      
        VS;const int MOD = 10000007;const int inf = 0x3f3f3f3f;const int maxn = 300; int n, m;char rel[10], ans[maxn];int dp[maxn][maxn]; int judge() {    for (int k = 1; k <= n; ++k)        for (int i = 1; i <= n; ++i)            for (int j = 1; j <= n; ++j)                dp[i][j] |= dp[i][k] & dp[k][j];     int state = 1;    for (int i = 1; i <= n; i++) {        if (dp[i][i]) return -1;        for (int j = i + 1; j <= n; j++) {            if (!(dp[i][j] | dp[j][i])) state = 0;        }    }    return state;} void get_ans(){    for (int i = 1; i <= n; i++) {        int pos = n;        for (int j = 1; j <= n; j++)            if (dp[i][j]) pos--;        ans[pos] = char(i + 'A' - 1);    }    ans[n + 1] = 0;} int main() {    //freopen("in.txt", "r", stdin);    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);    while (cin >> n >> m && n && m) {        ms(dp, 0);        int state = 0, success_ans = 0, failure_ans = 0;        for (int i = 1; i <= m; i++) {            scanf("%s", rel);            if (state) continue;            int x = rel[0] - 'A' + 1;            int y = rel[2] - 'A' + 1;            dp[x][y] = 1;            state = judge();            if (state == 1 && success_ans == 0) success_ans = i;            if (state == -1) failure_ans = i;        }         if (state == 1) {            get_ans();            printf("Sorted sequence determined after %d relations: %s.\n", success_ans, ans + 1);        }        else if (state == -1) {            printf("Inconsistency found after %d relations.\n", failure_ans);        }        else {            printf("Sorted sequence cannot be determined.\n");        }    }    return 0;}
      
     
    
   

F题 Sightseeing trip

#include
   
    using namespace std;#define ms(a,b) memset(a,b,sizeof a)const int maxn = 310;const int inf = 0x3f3f3f3f;int a[maxn][maxn], d[maxn][maxn], pos[maxn][maxn];int n, m, ans = inf;vector
    
      path; void get_path(int x, int y) {    if (pos[x][y] == 0)return;    get_path(x, pos[x][y]);    path.push_back(pos[x][y]);    get_path(pos[x][y], y);} int main() {    //freopen("in.txt", "r", stdin);    ios::sync_with_stdio(false), cin.tie(0);    int x, y, z;    cin >> n >> m;    ms(a, 0x3f);    for (int i = 1; i <= n; ++i)a[i][i] = 0;    while (m--) {        cin >> x >> y >> z;        a[x][y] = a[y][x] = min(a[y][x], z);    }     memcpy(d, a, sizeof a);    for (int k = 1; k <= n; k++) {        for (int i = 1; i < k; i++)            for (int j = i + 1; j < k; j++)                if ((long long)d[i][j] + a[j][k] + a[k][i] < ans) {                    ans = d[i][j] + a[j][k] + a[k][i];                    path.clear();                    path.push_back(i);                    get_path(i, j);                    path.push_back(j);                    path.push_back(k);                }        for (int i = 1; i <= n; i++)            for (int j = 1; j <= n; j++)                if (d[i][j] > d[i][k] + d[k][j]) {                    d[i][j] = d[i][k] + d[k][j];                    pos[i][j] = k;                }    }    if (ans == 0x3f3f3f3f) {        puts("No solution.");        return 0;    }    for (auto p : path)        cout << p << " ";    cout << endl;}
    
   

G题 Cow Relays

思路：

给出一张无向连通图，求S到E经过k条边的最短路。

矩阵我不熟,看了大佬的一个式子:

把经过xx个点的最短路的邻接矩阵\(X\)和经过\(y\)个点的最短路的邻接矩阵\(Y\)合并的式子为:

把输入转成邻接矩阵后,这个邻接矩阵可以看作恰好经过一个点的最短路,然后转移n−1n−1次就可以了

矩阵相乘时,需要使用优化

AC代码

#include
   
    using namespace std;int num[1000005], n, s, t, e, tol, x, y, z;struct map {    int data[500][500];    map operator*(const map& other) const {        map c;        for (int k = 1; k <= tol; k++)            for (int i = 1; i <= tol; i++)                for (int j = 1; j <= tol; j++)                    c.data[i][j] =                    min(c.data[i][j], data[i][k] + other.data[k][j]);        return c;    }    map() { memset(data, 0x3f3f3f3f, sizeof(data)); }} dis, ans;inline int input() { int t; scanf("%d", &t);  return t; }int main() {    n = input() - 1, t = input(), s = input(), e = input();    for (int i = 1; i <= t; i++) {        x = input();        if (!num[y = input()])num[y] = ++tol;        if (!num[z = input()])num[z] = ++tol;        dis.data[num[y]][num[z]] = dis.data[num[z]][num[y]] = x;    }    ans = dis;    while (n) (n & 1) && (ans = ans * dis, 0), dis = dis * dis, n >>= 1;    printf("%d", ans.data[num[s]][num[e]]);}