牛客 小白月赛16 小雨坐地铁 （分层最短路|优化建图）2019暑期多校训练营（第六场）D move

一种优化分层图建图方法

直接暴力建这样线特别乱得图 因为中转得关系 我们得暴力扫完这些中转
用一个虚拟点代表中专 这样建就 直接处理得换线得问题了

考虑分层图最短路。
很容易想到建 m 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 O(nm^2)的，可能会超时。
我们可以多建一层虚点，所有点到它对应的虚点不需要代价，从虚点到它对应的点需要对应的代价，这样就可以优化到 O(nm) 建图。最后跑一边最短路就好了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 1e3 + 5;
 
int n, m, s, t;
int head[500 * maxn], cnt;
int to[maxn * 1000], nxt[maxn * 1000], val[maxn * 1000];
 
void ade(int a, int b, int c) {
    to[++ cnt] = b, val[cnt] = c;
    nxt[cnt] = head[a], head[a] = cnt;
}
 
bool vis[maxn * 500];
int dis[maxn * 500];
void dijkstra(){
    priority_queue<P> que;
    que.push(P(0, s));
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    while(!que.empty()) {
        P p = que.top(); que.pop();
        int u = p.second;
        if(u == t) {
            cout << -p.first << endl;
            return ;
        }
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if(dis[v] > dis[u] + val[i]) {
                dis[v] = dis[u] + val[i];
                que.push(P(-dis[v], v));
            }
        }
    }
    cout << -1 << endl;
}
 
int main(){
    cin >> n >> m >> s >> t;
    for(int i = 1, a, b, c; i <= m; i ++) {
        cin >> a >> b >> c;
        for(int j = 1, u, v; j <= c; j ++) {
            cin >> v;
            if(j > 1)
                ade((i - 1) * n + u, (i - 1) * n + v, b), \
                ade((i - 1) * n + v, (i - 1) * n + u, b);
             
            ade((i - 1) * n + v, m * n + v, 0), \
            ade(m * n + v, (i - 1) * n + v, a);
            u = v;
        }
    }
    t = n * m + t;
    s = n * m + s;
    dijkstra();
    return 0;
}

牛客 多校 6场 D题 move

选择 K个变费用0 这个图建立起 没有什么边得互相限制
只有处理K
所以就不像上面呢样难了 只有K层图 每次图都一样 限制得K 只改变这次路得费用

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int cas, n, m;
int a[maxn];

bool chk(int mid) {
    bool vis[maxn] = {0};
    int res = 0, v = 0;
    for(int i = 1; i <= m; i ++) {
        v = 0;
        for(int j = n; j >= 1; j --) {
            if(mid - v >= a[j] && !vis[j]) {
                vis[j] = 1;
                v += a[j];
                res ++;
            }
        }
    }
    if(res != n) return 1;
    else return 0;
}

int main() {
	scanf("%d", &cas);
	for(int kk = 1; kk <= cas; kk ++) {
        scanf("%d %d", &n, &m);
        int sum = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            sum += a[i];
        }
        sort(a + 1, a + 1 + n);
        int l = sum / m, r = a[n] + sum / m;
        while(chk(l)) l ++;
        printf("Case #%d: %d\n", kk, l);
	}
    return 0;
}