头像

World_Devastator




离线:1个月前


活动打卡代码 AcWing 350. 巡逻

/*好题,别看它只是标为“简单” 
首先在不加边的情况下,这我们遍历这棵树的路线总长度是2*(n-1),每条边经过两次。
如果增加一条边,那么环上的每个点都可以少经过一次,为了让总长度最小,我们肯定
是选直径。最终答案为2*(n-1)-(L1-1)。考虑再加一条边,我们要求的是去除第一个环
上的边后的直径。有两可能,一是与第一个环不想交,那照做即可;二是相交,那么有
些边就会有重复。主要看第二种情况,本来每条边要经过两次,加入第一条边后,环上
的边经过次数少1,再加入一条边后,重复的边经过次数又减1,变成0了。但题目要求每
条边都要经过,所以必须再经过这条边两次了。我们可以得到一个做法:将第一个环上
的边权值都取反,变为-1,然后再找直径,最终答案为2*(n-1)-(L1-1)-(L2-1),可以发
现第二次加边时,如果出现重复的边,加上的权值为-1,这样刚好能和第一次抵消。

(重点)为什么第二次必须要用树形dp求直径?
第一次用两次搜索求是因为搜索修改路径比较方便。至于第二次,先看个图:
                    1
                  /  \
                2      3
              /   \     \
            4      5     6
          /       / \    / \ 
         7       8   9  10  11
显然第一次求出的直径是7-11,之后路径上的权值全变为-1,如果我们第二次求直径的时候
用两次搜索,不巧从10开始搜索的话,就会被一连串的-1给堵死,但事实上直径为3,是8-9。
感觉不太可能会出现这种情况,但数据大的时候谁也说不准。树形dp的正确性是因为它对每
个子树都求了一遍该子树内的最长直径,所以不会有遗漏。相比之下,两次搜索就有点取巧,
所以不能适应有负边的情况。

(强调)有负权边时,求直径用树形dp 
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Edge{
    int v, e, nxt;
}E[N << 1];
int n, m, point, last_point, sum, ans, tot = 1; //用到了成对变换找父节点,所以tot初始值为1 
int hd[N], dis[N], len[N << 1];
inline void add(int u, int v, int e){
    E[++tot] = (Edge){v, e, hd[u]}, hd[u] = tot;
}
void dfs(int u, int fath){ //两次搜索求直径 
    dis[u] = dis[fath] + 1;
    if (dis[u] > dis[point]) point = u;
    for (int i = hd[u]; i; i = E[i].nxt)
        if (E[i].v != fath)
            len[E[i].v] = i, dfs(E[i].v, u);
}
inline int calc(int x, int y){ //修改路径权值 
    int tmp = 0;
    while (x != y){
        tmp += E[len[x]].e;
        E[len[x]].e = E[len[x] ^ 1].e = -1; 
        x = E[len[x] ^ 1].v; //反向边的v就是它的父节点 
    }
    return tmp;
}
inline void dp(int u, int fath){ //树形dp求直径 
    for (int i = hd[u]; i; i = E[i].nxt){
        int v = E[i].v;
        if (v == fath) continue;
        dp(v, u);
        sum = max(sum, dis[u] + dis[v] + E[i].e);
        dis[u] = max(dis[u], dis[v] + E[i].e);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    ans = 2 * (n - 1);
    for (int i = 1; i < n; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v, 1), add(v, u, 1);
    }

    dfs(1, 0); last_point = point;
    dfs(point, 0);
    ans -= calc(point, last_point) - 1;

    if (m == 2){
        memset(dis, 0, sizeof dis);
        dp(1, 0);
        ans -= sum - 1;
    }

    printf("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 349. 黑暗城堡

/*这题也就看着吓人
其实这是一道板子题,最短路树。思路很简单,既然和最短路有关,肯定写求出1到所有点的最短路,
因为这里是稠密图,所以推荐用裸的Dijkstra。然后我们要建树,肯定是按最短路从小到大确定每个
点。对于一条边(u,v,e)我们想要取这条边当且仅当这条边满足dis[u]+e=dis[v],对于一个v可能用
许多u是满足条件的,所以就有多种情况。根据乘法原理,把每个点的方案数乘起来就是最终答案。 
*/ 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005, inf = 0x3f3f3f3f, mod = INT_MAX;
int n, m; ll ans = 1;
int s[N][N], dis[N], p[N], vis[N];
inline bool comp(int i, int j){
    return dis[i] < dis[j];
}
inline void Dijkstra(){ //最短路,裸的Dijkstra 
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    for (int i = 1; i <= n; ++i){
        int u = 0;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && dis[j] < dis[u]) u = j;
        vis[u] = 1;
        for (int v = 1; v <= n; ++v)
            if (s[u][v] != inf && dis[u] + s[u][v] < dis[v])
                dis[v] = dis[u] + s[u][v];
    }
}
inline void Work(){
    for (int i = 1; i <= n; ++i) p[i] = i;
    sort(p + 1, p + n + 1, comp); //从近到远确定 
    for (int i = 2; i <= n; ++i){
        int cnt = 0;
        for (int j = 1; j < i; ++j)
            if (dis[p[j]] + s[p[j]][p[i]] == dis[p[i]]) ++cnt; //满足条件 
        ans = ans * cnt % mod;
    }
}
int main(){
    scanf("%d%d", &n, &m);
    memset(s, 0x3f, sizeof s);
    for (int i = 1; i <= m; ++i){
        int u, v, e;
        scanf("%d%d%d", &u, &v, &e);
        s[u][v] = s[v][u] = min(s[u][v], e);
    }
    Dijkstra();
    Work();
    printf("%d", ans);
    return 0;
}



活动打卡代码 AcWing 348. 沙漠之王

/*嗯,这道题应该可以算作一类题的解题思路,最优比率生成树。
题目要求就是求出一颗生成树,使得Σ[i∈S]ci / Σ[i∈S]wi = k,其中k要最小,那么这个式子就等价
于 Σ[i∈S]ci - k * Σ[i∈S]wi = 0,考虑每条边就是Σ[i∈S]ci-k*wi = 0,然后观察到当k变大时,
结果随之变小,而我们的目的是要让k逼近0,所以当结果<=0时,说明k还有变小的余地,可以更优。然后,
这个式子显然满足单调性,所以我们可以二分k,然后因为我们想让k变小的余地尽可能大,那么生成树的
值要尽可能小,即做最小生成树,但需要将每条边的权值变为ci-k*wi。 
*/ 
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 1005, inf = 0x3f3f3f3f;
const db eps = 1e-5;
struct Node{ int x, y, z;}p[N];
struct Edge{ db c, w;}s[N][N];
int n, vis[N];
db dis[N];
inline db dist(Node a, Node b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
inline bool check(db mid){ //这里的图是完全图,所以用prim比Kruskal更优 
    memset(vis, 0, sizeof vis);
    for (int i = 0; i <= n; ++i) dis[i] = inf;
    dis[1] = 0;
    db ans = 0;
    for (int i = 1; i < n; ++i){ //选n-1条边 
        int u = 0;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && dis[j] < dis[u]) u = j;
        vis[u] = 1; //因为之前我把ans写在这里,而i<n,所以最后一个点没有被统计到,就WA了 
        for (int v = 1; v <= n; ++v)
            if (!vis[v]) dis[v] = min(dis[v], s[u][v].c - mid * s[u][v].w);
    }
    for (int i = 1; i <= n; ++i) ans += dis[i];
    return ans <= 0;
}
inline void solve(){
    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            s[i][j] = s[j][i] = (Edge){(db)abs(p[i].z - p[j].z), dist(p[i], p[j])}; //计算出长度和高度 
    db l = 0, r = 1000;
    while (l + eps < r){
        db mid = (l + r) / 2;
        if (check(mid)) r = mid; //要尽可能小 
        else l = mid;
    }
    printf("%.3lf\n", r);
}
int main(){
    while (1){
        scanf("%d", &n);
        if (!n) break;
        solve();
    }
    return 0;
}


活动打卡代码 AcWing 347. 野餐规划

/*这是一道好题,其中每个步骤各种变量都不一样(可能是我的问题),总之细节多
题面过于花里胡哨,其实就是:给定一张N个点M条边的无向图,求出无向图的一棵最小生成树,满足1号节点
的度数不超过给定的整数S。首先,去掉1号节点后,无向图分成若干个连通块,但是我们无需去划分这些,因
为我们可以把所有的边分成与1节点相连和不相连的,我们只对不与1相连的边做最小生成树,这样我们自然就
划分处理连通块。考虑所有与1相连的边,先从小到大排序,若v所在的连通块未连接,则与加入这条边。然后
我们就得到了一颗生成树,但这并不一定是最小的,因为一个连通块内部的点可能直接与1相连会更优。所以
我们在树上做dfs,算出1到每个点的路径上的最大值,若一个点与1相连且之前没有被用过,那么这就是我们的
备选边之一。假设我们一共有K个连通块,也就是说我们还有S-K次换边的机会,那么在备选边中选最优的S-K条
边,计算最终答案。 
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
struct Edge{ int u, v, e;}s[N];
struct S_Edge{ int v, e;}p[N];
struct Map_Edge{ int v, e, nxt;}E[N << 1];
int n, m, cnt, ans, block, tot, totS, tote, S;
int fa[N], hd[N], h[N], used[N], dis_max[N];
map<string, int> mp;
priority_queue<int> pq;
inline bool comp(Edge a, Edge b){ return a.e < b.e;} //用于排序与1节点不相连的边 
inline bool cmp(S_Edge a, S_Edge b){ return a.e < b.e;} //用于排序与1相连的边 
inline void add(int u, int v, int e){ E[++tote] = (Map_Edge){v, e, hd[u]}, hd[u] = tote;} //用于dfs 
int Find(int x){
    if (x == fa[x]) return x;
    return fa[x] = Find(fa[x]);
}
int dfs(int u, int fat){ //算出1到每个节点路径上的最大值 
    for (int i = hd[u]; i; i = E[i].nxt){
        int v = E[i].v;
        if (v == fat) continue;
        dis_max[v] = max(dis_max[u], E[i].e);
        dfs(v, u);
    }
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        string name1, name2; int val;
        cin >> name1 >> name2 >> val;
        if (name2 == "Park") swap(name1, name2);
        if (!mp[name1]) mp[name1] = ++cnt; //用map来为每个人分配编号 
        if (!mp[name2]) mp[name2] = ++cnt;

        if (name1 == "Park") p[++totS] = (S_Edge){mp[name2], val}; //分类加边 
        else s[++tot] = (Edge){mp[name1], mp[name2], val};
    } 
    cin >> m; S = mp["Park"];

    sort(s + 1, s + tot + 1, comp);
    for (int i = 1; i <= cnt; ++i) fa[i] = i; //请注意点集大小是cnt,之前WA在这里 
    for (int i = 1; i <= tot; ++i){
        int u = Find(s[i].u), v = Find(s[i].v);
        if (u == v) continue;
        ans += s[i].e;
        add(u, v, s[i].e), add(v, u, s[i].e); //选中了,加边 
        fa[v] = u;
    }

    for (int i = 1; i <= cnt; ++i) //算连通块个数,如果一个点自己就是并查集的根就说明有一个连通块 
        block += (Find(i) == i) * (i != S);

    sort(p + 1, p + totS + 1, cmp);
    for (int i = 1; i <= totS; ++i){ //1向各个连通块连边 
        if (h[Find(p[i].v)]) continue; //说明该个点所在的连通块已经连入 
        h[Find(p[i].v)] = 1; used[i] = 1; //used是为了之后换边时跳过已经使用的边 
        ans += p[i].e;
        add(S, p[i].v, p[i].e), add(p[i].v, S, p[i].e); //也需要加入生成树中 
    }

    dfs(S, 0); //计算dis_max 
    for (int i = 1; i <= totS; ++i){
        if (used[i]) continue;  
        pq.push(dis_max[p[i].v] - p[i].e); //把换边后能降低的代价放入大根堆中,肯定减得多的更优 
    }
    //注意这里的三个结束条件:没有换边的机会了、可用的边没了、当前换边不会更优了。之前这里没写全,WA了 
    for (int i = 1; i <= m - block && pq.size() && pq.top() > 0; ++i) 
        ans -= pq.top(), pq.pop();

    cout << "Total miles driven: " << ans << endl;
    return 0;
}



活动打卡代码 AcWing 346. 走廊泼水节

/*Kruskal练手题
首先最小生成树有一个结论:给定一张无向图G=(V,E),n=|V|,m=|E|。
从E中选出k<n-1条边构成G的生成树森林。若再从m-k条边中选出n-1-k 
边使其成为G的生成树,且选出的边的权值和最小,那么一定包含m-k
条边中连接两个生成树森林的权值最小的边。
此题我们用Kruskal的思想,将边按权值排序,对于当前的一条边(u,v,e),
若Su!=Sv,由结论可知,e一定是所有Su向Sv连边中最小的,即添加的边
都应该大于e,所以最小为e+1,又因为Su和Sv中的点两两连边共有|Su|*|Sv|
条,再减去一条(u,v,e),所以这条边对答案的贡献是e+1*(|Su|*|Sv|-1)。 
可知这一定是正确的,对于除Su与Sv连的边之外的所有边,都取决于排名在
(u,v,e)之后,那么e'>e,则那条边连接的两个集合的连边一定大于e+1,这
就与(u,v,e)没关系了。 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6005;
struct Edge{
    int u, v, e;
}s[N];
int T, n, fa[N], sz[N];
ll ans; 
inline void clear(){
    ans = 0;
    for (int i = 1; i <= n; ++i)
        fa[i] = i, sz[i] = 1;
}
inline bool comp(Edge a, Edge b){
    return a.e < b.e;
}   
int Find(int x){
    if (fa[x] == x) return x;
    return fa[x] = Find(fa[x]);
}
inline void Merge(int x, int y){
    fa[y] = x, sz[x] += sz[y];
}
int main(){
    scanf("%d", &T);
    while (T --){
        scanf("%d", &n);
        clear(); //清空 
        for (int i = 1; i < n; ++i)
            scanf("%d%d%d", &s[i].u, &s[i].v, &s[i].e);
        sort(s + 1, s + n, comp);
        for (int i = 1; i < n; ++i){ //Kruskal
            int u = Find(s[i].u), v = Find(s[i].v);
            if (u == v) continue;
            ans += (ll)(s[i].e + 1) * (sz[u] * sz[v] - 1); //算贡献,别忘开long long 
            Merge(u, v);
        }
        printf("%lld\n", ans);
    }
    return 0;
}



活动打卡代码 AcWing 345. 牛站

/*算是一个矩阵乘法优化DP吧
首先,我们需要把点离散化,不然点集有1000。不难算出转移方程是
B[i,j]=min[1<=k<=p]{A[i,k]+A[k,j]}那么我们假设矩阵A的m次方, 
A^m[i,j],表示i到j经过m条边的最短路,进一步,我们可以推出式子
A^(r+m)[i,j]=min[1<=k<=p]{A^r[i,k]+A^m[k,j]}对比矩阵乘法,其
实这个式子就是一个广义的矩阵乘法。而矩阵乘法的快速幂的要求是
满足结合律,显然min也满足结合律,所以可以快速幂处理。 
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int n, m, S, T, tot, a[N];
struct Edge{
    int u, v, e;
}s[N];
struct Matrix{ //以下为矩阵的一些基本操作 
    int mt[N][N];
    Matrix(){
        memset(mt, 0x3f, sizeof mt); 
    }
    Matrix operator *(const Matrix t){
        Matrix ans;
        for (int i = 1; i <= tot; ++i)
            for (int j = 1; j <= tot; ++j)
                for (int k = 1; k <= tot; ++k)
                    ans.mt[i][j] = min(ans.mt[i][j], mt[i][k] + t.mt[k][j]);
        return ans;
    }
}mat;
inline Matrix unit(){
    Matrix tmp;
    for (int i = 1; i <= tot; ++i) //同一个点之间的距离是0 
            tmp.mt[i][i] = 0;
    return tmp;
}
inline Matrix qpow(Matrix a, int b){ //快速幂 
    Matrix tmp = unit();
    for (; b; b >>= 1, a = a * a)
        if (b & 1) tmp = tmp * a;
    return tmp;     
}
int main(){
    scanf("%d%d%d%d", &n, &m, &S, &T);
    for (int i = 1; i <= m; ++i){
        scanf("%d%d%d", &s[i].e, &s[i].u, &s[i].v);
        a[i * 2 - 1] = s[i].u;
        a[i * 2] = s[i].v;  
    }
    sort(a + 1, a + m * 2 + 1);
    tot = unique(a + 1, a + m * 2 + 1) - a - 1; //离散化 
    for (int i = 1; i <= m; ++i){
        s[i].u = lower_bound(a + 1, a + tot + 1, s[i].u) - a;
        s[i].v = lower_bound(a + 1, a + tot + 1, s[i].v) - a;
        int u = s[i].u, v = s[i].v;
        mat.mt[u][v] = mat.mt[v][u] = min(mat.mt[u][v], s[i].e); //建图 
    }
    S = lower_bound(a + 1, a + tot + 1, S) - a;
    T = lower_bound(a + 1, a + tot + 1, T) - a;
    mat = qpow(mat, n); //快速幂 
    printf("%d\n", mat.mt[S][T]);
    return 0;
}



活动打卡代码 AcWing 344. 观光之旅

/*波折的题目,发现最后是没开long long 
可以说这道题是个板子,关于用Floyd求无向图最小环问题。我们考虑Floyd的过程,
当最外层为k时,目前d[x][y]中,保存着是经过编号不超过k-1的节点构成的从i到
j的最短路长度。于是min[1<=i<j<k]{d[i][j]+f[j][k]+f[k][j]}就表示,由编号不
超过k的节点且一定含有k节点构成的环。i,j相当于枚举了k的相邻节点,所以三个
点的条件满足,可以证明这一定不会漏情况。 
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105, inf = 0x3f3f3f3f;
int n, m, ans = inf, f[N][N], d[N][N], pos[N][N];
vector<int> path;
void get_path(int u, int v){ //找u到v的最短路中经过的点 
    if (!pos[u][v]) return;
    get_path(u, pos[u][v]);
    path.push_back(pos[u][v]);
    get_path(pos[u][v], v);
}
int main(){
    scanf("%d%d", &n, &m);
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) f[i][i] = 0;
    for (int i = 1; i <= m; ++i){
        int u, v, e;
        scanf("%d%d%d", &u, &v, &e);
        f[u][v] = f[v][u] = min(f[u][v], e);
    }

    memcpy(d, f, sizeof f); //我们需要原图和最短路图 
    for (int k = 1; k <= n; ++k){
        for (int i = 1; i < k; ++i) //注意不超过k 
            for (int j = i + 1; j < k; ++j) 
                if ((ll)d[i][j] + f[j][k] + f[k][i] < ans){
                    ans = d[i][j] + f[j][k] + f[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) //继续Floyd,更新d 
            for (int j = 1; j <= n; ++j)
                if (d[i][k] + d[k][j] < d[i][j]){
                    d[i][j] = d[i][k] + d[k][j]; pos[i][j] = k;
                }
    }

    if (ans == inf){
        puts("No solution."); return 0;
    }
    for (int i = 0; i < path.size(); ++i)
        printf("%d ", path[i]);
    puts("");
    return 0;
}



活动打卡代码 AcWing 343. 排序

/*Floyd传递闭包
对于每个条件u<v,令F[u][v]=1表示u比v小。我们可以在每读入一个条件时,就做一遍Floyd,
实时更新数据。然后暴力判断,我们需要判断出两种特殊情况:出现矛盾、用当前及之前的关
系已经能判断出所有数的大小关系。出现矛盾是指A>B且A<B,当然可能是个更复杂的关系,但
我们可以发现,这一定是一个环,那么必然会出现A<A,所以我们只要判断这个即可。对于第二
种,若u!=v,且F[u][v]==0 && F[v][u]==0 即没有大小关系,就无法判断,反之,若所有数据
都具有了大小关系,就结束了。输出大小关系做拓扑排序,需注意,在原图上做,不然关系会
混乱。 
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n, m, F[N][N], G[N][N], In_Degree[N];
queue<int> q;
inline void Clear(){
    memset(F, 0, sizeof F);
    memset(G, 0, sizeof G);
    memset(In_Degree, 0, sizeof In_Degree);
}
inline void Floyd(){
    for (int k = 0; k < n; ++k)
         for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                F[i][j] |= F[i][k] & F[k][j];
}
inline void Work(int T){ //拓扑排序 
    for (int i = 0; i < n; ++i)
        if (!In_Degree[i]) q.push(i);
    printf("Sorted sequence determined after %d relations: ", T);
    while (q.size()){
        int u = q.front(); q.pop();
        putchar(u + 'A');
        for (int v = 0; v < n; ++v)
            if (G[u][v]){
                --In_Degree[v];
                if (!In_Degree[v]) q.push(v);
            }
    }
    puts(".");
}
inline void Solve(){
    int Fail = 0, Not_Find = 0, T;
    for (int i = 1; i <= m; ++i){
        char st[10];
        scanf(" %s", st);
        if (Not_Find || Fail) continue; //满足两种特殊情况之一 
        char u = st[0] - 'A', v = st[2] - 'A';

        F[u][v] = G[u][v] = 1; //关系图和原图 
        ++In_Degree[v]; //入度,之后做拓扑排序 
        Floyd();

        Not_Find = 1;
        for (int u = 0; u < n; ++u){
            if (F[u][u]){Fail = 1; break;} //出现矛盾 
            for (int v = 0; v < n; ++v)
                if (u != v && !F[u][v] && !F[v][u]) Not_Find = 0; //没有找到大小关系,任不能判断 
        }

        T = i;
    }
    if (Fail) printf("Inconsistency found after %d relations.\n", T);
    else if (!Not_Find) printf("Sorted sequence cannot be determined.\n");
    else Work(T);
}
int main(){
    while (1){
        Clear();
        scanf("%d%d", &n, &m);
        if (n + m == 0) break;
        Solve();
    }
    return 0;
}



活动打卡代码 AcWing 342. 道路与航线

/*像这种看似很简单实则复杂的题是很有思维含量的 
这题的数据被特殊构造过,纯spfa跑不过。所以我们要另寻出路,发现题目中有这么多的限制
条件,需要加以利用。题目中的边分为单向边和双向边,其中双向边保证非负,那么我们可以
先加入双向边,这样就构成了几个连通块,可以看做一个点。而单向边就是将各个“点”连接
起来。因为题目中说了单向边不可能在一个环上,所以缩点后的图应该是一个DAG,保证连通块
内不可能有单向边,不然一定不满足要求。所以整体我们可以用拓扑序处理,然后每个连通块
内用Dijsktra跑比较好。
具体思路:1.只加入双向边,划分连通块,每个点连通块所属编号即为c[x]。
          2.加入单向边,统计连通块的入度deg[i]。
          3.用一个队列做拓扑序,将入度为0的连通块入队。 
          4.取出队首连通块,做Dijsktra
                Dijsktra的具体步骤:
                (1)将所有点入堆(因为我们并不知道具体有哪些点被更新了,全部入堆比较方便)
                (2)取出x,扩展过就跳过,不然扫描所有出边,用dis[x]+e更新dis[y]
                (3)若c[x]==c[y],且y被更新了,就入堆
                (4)若c[x]!=c[y],那么deg[c[y]]减一。若成了0,则将c[y]入队,加入拓扑序中 
                (5)重复以上步骤,直到堆空 
          5.重复以上步骤,直到队列为空 

关于用Dijsktra的正确性:首先如果不走上连通块与连通块相连的单向边,答案一定是对的,但
这和一般图的区别是,在我们的方案下负权边是一定一条路径的最后一条边了。所以就算更新有
错,也不会祸害其他点,当全部做完之后,那个点的答案也是对的

关于判无解是dis[i] >= inf/2的原因:假设这么一张DAG:a->c d->b b->c 起点在a中,事实上b和 
d都不会经过,但做完a后,d中的点全是inf,但有可能通过负权单向边使得结果比b中的inf点小。 
*/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 25005, M = 50005, inf = 0x3f3f3f3f;
struct Edge{
    int v, e, nxt;
}E[M * 3];
int T, R, P, S, cnt, tot, hd[N];
int c[N], dis[N], deg[N], vis[N];
vector<int> point[N];
priority_queue<pii, vector<pii>, greater<pii> > p;
queue<int> q;
inline void add(int u, int v, int e){
    E[++tot] = (Edge){v, e, hd[u]}, hd[u] = tot;
}
void dfs(int u){
    c[u] = cnt; point[cnt].push_back(u);
    for (int i = hd[u]; i; i = E[i].nxt)
        if (!c[E[i].v]) dfs(E[i].v);
}
inline void Dijkstra(int id){
    for (int i = 0; i < point[id].size(); ++i) //无脑入队 
        p.push({dis[point[id][i]], point[id][i]});
    while (p.size()){ //Dijsktra板子 
        int u = p.top().second; p.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = hd[u]; i; i = E[i].nxt){
            int v = E[i].v;
            if (c[u] == c[v]){ //分类讨论 
                if (dis[u] + E[i].e < dis[v])
                    dis[v] = dis[u] + E[i].e, p.push({dis[v], v});
            }else{
                if (dis[u] + E[i].e < dis[v]) dis[v] = dis[u] + E[i].e;
                --deg[c[v]];
                if (!deg[c[v]]) q.push(c[v]);
            }
        }
    }   
}
int main(){
    scanf("%d%d%d%d", &T, &R, &P, &S);
    for (int i = 1; i <= R; ++i){
        int u, v, e;
        scanf("%d%d%d", &u, &v, &e);
        add(u, v, e), add(v, u, e);
    }

    /*解释一下这里为什么不用保证S所在连通块必须先入队 
    以为第一批入队的连通块没有入度,也就是说S不可能更新到这些点,所以就不用特判了 
    */ 
    for (int i = 1; i <= T; ++i) //划分连通块 
        if (!c[i]) ++cnt, dfs(i);

    for (int i = 1; i <= P; ++i){
        int u, v, e;
        scanf("%d%d%d", &u, &v, &e);
        add(u, v, e);
        if (c[u] != c[v]) ++deg[c[v]]; //入度 
    }

    for (int i = 1; i <= cnt; ++i)
        if (!deg[i]) q.push(i);
    memset(dis, 0x3f, sizeof dis);
    dis[S] = 0;
    while (q.size()){ //拓扑排序 
        Dijkstra(q.front()); q.pop();
    }

    for (int i = 1; i <= T; ++i){
        if (dis[i] >= inf / 2) puts("NO PATH");
        else printf("%d\n", dis[i]);
    }
    return 0;
}




活动打卡代码 AcWing 341. 最优贸易

/*基础题
其实这道题目的意思就是找到一条1到n的路径,使得该路径上的最大值和最小值的差最大。
直接求肯定是不现实的,分开求有不能确定路径的合法性,这里是一个常用的技巧,将1到n
的路径,拆为1到x的路径和x到n的路径,x就相当于中转站。对于1到x的路径,我们用dis[0][x]
表示1到x路径上的最小值;对于x到n的路径,我们需要先建一张反图,用dis[1][x]表示x到
n路径上的最大值。可知这并不满足Dijsktra,所以要用spfa实现。答案可以即是所有点中
dis[1][x]-dis[0][x]的最大值。可以证明不会有遗漏情况。

当初的疑惑:万一最终的最大值和最小值都在x到n的路径上怎么办
那么如果这是最终答案,一定会另有一个x成为中转站,分割路径使得它们分属1到x和x到n
的路径上 
*/ 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5, inf = 0x3f3f3f3f;
struct Edge{
    int v, nxt;
}E[2][M * 2];
int n, m, ans;
int tot[2], hd[2][N], vis[N], dis[2][N], price[N]; 
queue<int> q;
inline void add0(int u, int v){ //存图 
    E[0][++tot[0]] = (Edge){v, hd[0][u]}, hd[0][u] = tot[0];
}
inline void add1(int u, int v){ //存反图 
    E[1][++tot[1]] = (Edge){v, hd[1][u]}, hd[1][u] = tot[1];
}
inline int check(int u, int v, int type){ //都是为了偷懒只写一个spfa 
    if (type == 0) return min(dis[type][u], price[v]) < dis[type][v];
    else return max(dis[type][u], price[v]) > dis[type][v];
}
inline int calc(int u, int v, int type){
    if (type == 0) return min(dis[type][u], price[v]);
    else return max(dis[type][u], price[v]);
}
inline void spfa(int origin, int type, int origin_val){
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i)
        dis[type][i] = origin_val;
    dis[type][origin] = price[origin];
    q.push(origin);
    while (q.size()){
        int u = q.front(); q.pop();
        vis[u] = 0;
        for (int i = hd[type][u]; i; i = E[type][i].nxt){
            int v = E[type][i].v;
            if (check(u, v, type)){ //更新最大或最小值 
                dis[type][v] = calc(u, v, type);
                if (!vis[v]) q.push(v), vis[v] = 1;
            }
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", price + i);
    for (int i = 1; i <= m; ++i){
        int u, v, type;
        scanf("%d%d%d", &u, &v, &type);
        if (type == 1) add0(u, v);
        else add0(u, v), add0(v, u);    

        if (type == 1) add1(v, u);
        else add1(v, u), add1(u, v);
    }
    spfa(1, 0, inf);
    spfa(n, 1, -inf);
    for (int i = 1; i <= n; ++i) //枚举答案 
        ans = max(ans, dis[1][i] - dis[0][i]);
    printf("%d\n", ans);
    return 0;
}