Graph Theory

POJ2449.cpp

// #include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)
#define print(s) std::cout << s << std::endl
#define pii pair<int, int> 

using namespace std;
// using pii = std::pair<int, int>;

const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 100;

vector<pii> G[maxn], rev_G[maxn];
vector<int> dist;
int n, m;

struct triple{
    int a, b, c;
    bool operator > (const triple other) const{
        if(a != other.a) return a > other.a;
        if(b != other.b) return b > other.b;
        return c > other.c; 
    }
};

void dij(int u){
    dist[u] = 0;
    priority_queue<pii , vector<pii>, greater<pii> > que;
    que.push({0, u});
    while(!que.empty()){
        pii st = que.top();
        que.pop();
        if(st.first > dist[st.second]) continue;
        for(int i=0; i<rev_G[st.second].size(); i++){
            pii edge = rev_G[st.second][i];
            if(dist[edge.first] > st.first + edge.second){
                dist[edge.first] = st.first + edge.second;
                que.push({dist[edge.first], edge.first});
            }
        }
    }
}

ll a_start(int s, int t, int k){
    if(dist[s] == inf) return -1; // 不可达
    priority_queue<triple, vector<triple>, greater<triple> > que;
    que.push({0 + dist[s], 0, s});
    while(!que.empty()){
        triple st = que.top();
        que.pop();
        if(st.c == t) k--;
        if(k == 0) return st.b;
        for(int i=0; i<G[st.c].size(); i++){
            pii edge = G[st.c][i];
            que.push({dist[edge.first] + st.b + edge.second, st.b + edge.second, edge.first});
        }
    }
    return -1;
}

void solve() {
    cin >> n >> m;
    int s, t, k;
    for(int i=0; i<m; i++){
        cin >> s >> t >> k;
        G[s].push_back({t, k});
        rev_G[t].push_back({s, k});
    }
    cin >> s >> t >> k;
    if(s == t) k++; // 由于当s==t时，"最短路"长度为0，但是他不算是一条路径
    dist = vector<int>(n + 1, inf);
    dij(t);
    cout << a_start(s, t, k) << endl;
}

signed main() {
    Android;
    solve();
}

POJ3463.cpp

// #include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)
#define print(s) std::cout << s << std::endl
#define pii pair<int, int> 

using namespace std;
// using pii = std::pair<int, int>;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e3 + 100;
const int buffer_size = 3e6;

vector<pii> G[maxn];
int dist[maxn];
int cnt[maxn], cnt_x[maxn];
bool inqueue[maxn];
int n, m, s, e;
int ans_0, ans_1;

void dij(int k){
    memset(inqueue, 0, sizeof inqueue);
    dist[k] = 0;
    cnt[k] = 1;
    priority_queue<pii , vector<pii>, greater<pii> > que;
    que.push({0, k});
    // 使用cnt数组，避免一个点多次入队
    while(!que.empty()){
        pii st = que.top();
        que.pop();
        int u = st.second;
        inqueue[u] = false;
        if(u == e) continue;
        if(st.first > dist[st.second] + 1) continue;
        for(int i=0; i<G[st.second].size(); i++){
            pii edge = G[st.second][i];
            int v = edge.first, d = edge.second;
            if(dist[v] + 1 == st.first + d) { // 次短路
                cnt_x[v] += st.first==dist[u]?cnt[u]:cnt_x[u];
                if(!inqueue[v])  que.push({st.first + d, v}), inqueue[v]=true;
            }
            if(dist[v] == st.first + d){ // 最短路
                cnt[v] += st.first==dist[u]?cnt[u]:cnt_x[u];
                cnt_x[v] += st.first==dist[u]?cnt_x[u]:0;
                if(!inqueue[v]) que.push({dist[v], v}), inqueue[v]=true;
            }
            if(dist[v] > st.first + d){ // 松弛
                cnt_x[v] = (dist[v] == st.first + d + 1)?cnt[v]:0;
                cnt[v] = st.first==dist[u]?cnt[u]:cnt_x[u];
                cnt_x[v] += st.first==dist[u]?cnt_x[u]:0;
                inqueue[v]=true;
                dist[v] = st.first + d;
                que.push({dist[v], v});
            }
        }
        cnt[u] = cnt_x[u] = 0;
    }
}

void solve() {
    ans_0 = ans_1 = 0;
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(cnt_x, 0, sizeof cnt_x);
    cin >> n >> m;
    for(int i=0; i<=n; i++) G[i].clear();
    for(int i=0; i<m; i++){
        int a, b, l;
        cin >> a >> b >> l;
        G[a].push_back({b, l});
    }
    cin >> s >> e;
    dij(s);
    cout << cnt[e] + cnt_x[e] << endl;
}

signed main() {
    Android;
    int t; cin >> t;
    while(t--) solve();
}

POJ3613.cpp

// #include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <map>
#include <cstdio>
#include <cstring>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)
#define print(s) std::cout << s << std::endl
#define pii pair<int, int> 

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;

int n, t, s, e;

struct matrix{
    int v[maxn][maxn];
    matrix(){memset(v, 0x3f, sizeof v);} // 因为必须要走n段路，所以主对角线上不能为0
};

matrix operator * (const matrix & m1, const matrix & m2){
    matrix ret;
    for(int k=0; k<t; k++){
        for(int i=0; i<t; i++){
            for(int j=0; j<t; j++)
                ret.v[i][j] = min(ret.v[i][j], m1.v[i][k] + m2.v[k][j]);
        }
    }
    return ret;
}

matrix qpow(matrix & base, int n){
    matrix ret;
    F(i, t) ret.v[i][i] = 0;
    while(n){
        if (n & 1) ret = ret * base;
        base = base * base;
        n >>= 1;
    }
    return ret;
}

void solve() {
    cin >> n >> t >> s >> e;
    int l, u, v, idx=0;
    matrix base;
    map<int, int> name_idx;
    for(int i=0; i<t; i++){
        cin >> l >> u >> v;
        if(name_idx.find(u)==name_idx.end()) name_idx[u] = idx++;
        if(name_idx.find(v)==name_idx.end()) name_idx[v] = idx++;
        u = name_idx[u], v = name_idx[v];
        base.v[u][v] = base.v[v][u] = l;
    }
    matrix result = qpow(base, n);
    cout << result.v[name_idx[s]][name_idx[e]] << endl;
}

signed main() {
    Android;
    solve();
}