kuangbin 4 最短路

#include <iostream>
using namespace std;
const int maxpoint = 1e3+9;
const int maxedges = 2e3+9;
const int inf = (1<<31)-1;
int n, m, ta, tb, tc, d[maxpoint], tem, vis[maxpoint], v;
struct node {
    int to, nt, val;
}edges[maxedges<<1];int head[maxpoint], tot;

void addedge(int from, int to, int val) {
    edges[++tot].to = to;
    edges[tot].val = val;
    edges[tot].nt = head[from];
    head[from] = tot;
}

void dijkstra(int bg, int ed) {
    for (int i = 1; i <= n; ++i) d[i] = inf;
    d[bg] = 0;
    for (int i = 1; i <= n; ++i) {
        tem = inf;
        for (int j = 1; j <= n; ++j) if (!vis[j] && tem > d[j]) tem = d[v=j];
        vis[v] = 1;
        for (int j = head[v]; j; j=edges[j].nt) {
            int to = edges[j].to;
            if (!vis[to] && d[to] > d[v]+edges[j].val) d[to] = d[v]+edges[j].val;
        }
    }
    printf("%d\n", d[ed]);
}

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &ta, &tb, &tc);
        addedge(ta, tb, tc);addedge(tb, ta, tc);
    }
    dijkstra(n, 1);
    return 0;
}

#include <iostream>
using namespace std;
const int maxpoint = 1e3+9;
const int maxedges = 1e5+9;
const int inf = (1<<31)-1;
int n, m, k, from[maxedges<<1], to[maxedges<<1], val[maxedges<<1], d[maxpoint], tem, vis[maxpoint], v, ans[maxpoint], fin;
struct node {
    int to, nt, val;
}edges[maxedges<<1];int head[maxpoint], tot;
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))

void addedge(int from, int to, int val) {
    edges[++tot].to = to;
    edges[tot].nt = head[from];
    edges[tot].val = val;
    head[from] = tot;
}

void dijkstra(int bg) {
    for (int i = 1; i <= n; ++i) d[i] = inf;
    d[bg] = 0;
    for (int i = 1; i <= n; ++i) {
        tem = inf;
        for (int j = 1; j <= n; ++j) if (!vis[j] && tem > d[j]) tem = d[v=j];
        vis[v] = 1;
        for (int j = head[v]; j; j=edges[j].nt) {
            int to = edges[j].to;
            if (!vis[to] && d[to] > d[v]+edges[j].val) d[to] = d[v]+edges[j].val;
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; ++i) scanf("%d%d%d", from+i, to+i, val+i);
    // 正向建图
    for (int i = 1; i <= m; ++i) addedge(from[i], to[i], val[i]);
    dijkstra(k);
    for (int i = 1; i <= n; ++i) ans[i] = d[i];
    tot = 0;cl(vis, 0);cl(d, 0);cl(head, 0);
    // 反向建图
    for (int i = 1; i <= m; ++i) addedge(to[i], from[i], val[i]);
    dijkstra(k);
    for (int i = 1; i <= n; ++i) fin = max(fin, d[i]+ans[i]);
    printf("%d\n", fin);
    return 0;
}

#include <iostream>
using namespace std;
const int maxn = 109;
int n, m, mp[maxn][maxn], ta, tb, ans;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);
        mp[ta][tb] = 1;
    }
    // floyd
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (mp[i][k] && mp[k][j]) mp[i][j] = 1;
    for (int i = 1; i <= n; ++i) {
        int tem = 0;
        for (int j = 1; j <= n; ++j)
            if (mp[i][j] || mp[j][i]) tem++;
        if (tem == n-1) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

#include <iostream>
using namespace std;
typedef long long ll;
const int maxpoint = 1e6+9;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct node {
    ll to, nt, val;
}edges[maxpoint<<1];int head[maxpoint], tot;
ll t, n, m, ff[maxpoint], tt[maxpoint], vv[maxpoint], ans[maxpoint], d[maxpoint], tem, vis[maxpoint], v, fin;
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))

void addedge(ll from, ll to, ll val) {
    edges[++tot].to = to;
    edges[tot].val = val;
    edges[tot].nt = head[from];
    head[from] = tot;
}

// 堆优化
#include <queue>
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) d[i] = inf;
    d[s] = 0;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        ll nw = pq.top().second;pq.pop();
        if (!vis[nw]) {
            vis[nw] = 1;
            for (int i = head[nw]; i; i=edges[i].nt) {
                int to = edges[i].to;
                if (d[to] > d[nw]+edges[i].val) {
                    d[to] = d[nw]+edges[i].val;
                    if (!vis[to]) pq.push(make_pair(d[to], to));
                }
            }
        }
    }
}

int main() {
    scanf("%lld", &t);
    while (t--) {
        cl(d, 0);cl(vis, 0);cl(head, 0);tot = 0;fin = 0;
        scanf("%lld%lld", &n, &m);
        for (int i = 1; i <= m; ++i) {
            scanf("%lld%lld%lld", ff+i, tt+i, vv+i);
            addedge(ff[i], tt[i], vv[i]);
        }
        dijkstra(1);
        for (int i = 1; i <= n; ++i) ans[i] = d[i];
        cl(d, 0);cl(vis, 0);cl(head, 0);tot = 0;
        for (int i = 1; i <= m; ++i) addedge(tt[i], ff[i], vv[i]);
        dijkstra(1);
        for (int i = 1; i <= n; ++i) fin += ans[i]+d[i];
        printf("%lld\n", fin);
    }
    return 0;
}