裸SPFA解法。之后会用dij解一下。

//AC 24ms vector & queue & pair

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

const int N = 1100, M = 110000;

int n, m, k;
vector< pair<int,int> > d1[N], d2[N];
int posd[N],revd[N];

void spfa(const vector< pair<int,int> > d[], int e[]) {
    queue<int> q;
    bool inq[N];
    q.push(k);
    inq[k]^=1;
    e[k]=0;
    int t;
    while(!q.empty()){
        t = q.front();
        for(int i = 0, b, c; i < d[t].size(); i++){
            b=d[t][i].first;
            c=d[t][i].second;
            if(e[b]>e[t]+c){
                e[b] = e[t]+c;
                if(!inq[b]){
                    q.push(b);
                    inq[b]^=1;
                }
            }
        }
        q.pop();
        inq[t] ^= 1;
    }
}

int main() {
    cin>>n>>m>>k;
    for(int i = 0, a, b, c; i < m; i++) {
        cin>>a>>b>>c;
        d1[a].push_back(make_pair(b,c));
        d2[b].push_back(make_pair(a,c));
    }
    memset(posd, 0x3f, sizeof(posd));
    memset(revd, 0x3f, sizeof(revd));
    spfa(d1, posd);
    spfa(d2, revd);
    int x = 0;
    for(int i = 1, t; i <= n; i++){
        t= posd[i]+revd[i];
        if(t>10000) continue;
        if(x<t) x = t;
    }
    cout<<x<<endl;
    return 0;
}
//AC 17ms vector & struct

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

const int N = 1100, M = 110000;

struct edge{
    int t, v;
};

int n, m, k;
vector< edge > d1[N], d2[N];
int posd[N],revd[N];

void spfa(const vector< edge > d[], int e[]) {
    queue<int> q;
    bool inq[N];
    q.push(k);
    inq[k]^=1;
    e[k]=0;
    int t;
    while(!q.empty()){
        t = q.front();
        for(int i = 0, b, c; i < d[t].size(); i++){
            b=d[t][i].t;
            c=d[t][i].v;
            if(e[b]>e[t]+c){
                e[b] = e[t]+c;
                if(!inq[b]){
                    q.push(b);
                    inq[b]^=1;
                }
            }
        }
        q.pop();
        inq[t] ^= 1;
    }
}

int main() {
    cin>>n>>m>>k;
    edge e;
    for(int i = 0, a, b, c; i < m; i++) {
        cin>>a>>b>>c;
        e.t=b; e.v=c;
        d1[a].push_back(e);
        e.t=a;
        d2[b].push_back(e);
    }
    memset(posd, 0x3f, sizeof(posd));
    memset(revd, 0x3f, sizeof(revd));
    spfa(d1, posd);
    spfa(d2, revd);
    int x = 0;
    for(int i = 1, t; i <= n; i++){
        t= posd[i]+revd[i];
        if(t>10000) continue;
        if(x<t) x = t;
    }
    cout<<x<<endl;
    return 0;
}
//AC 25ms 链式前向星

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

const int N = 1100, M = 110000;

struct Edge {
    int to, pre, w;
};

void inline addedge(Edge e[], int from, int to, int w, int & cnt, int head[]) {
    e[cnt].to = to;
    e[cnt].pre = head[from];
    e[cnt].w = w;
    head[from] = cnt++;
}

Edge pose[M], reve[M];
int posd[N], revd[N], posh[N], revh[N], posc, revc, n, m, k;

void spfa(const Edge d[], int e[], const int h[]) {
    queue<int> q;
    bool inq[N];
    q.push(k);
    inq[k] ^= 1;
    e[k] = 0;
    int t;
    while(!q.empty()) {
        t = q.front();
        for(int i = h[t], b, c; ~i; i = d[i].pre) {
            b = d[i].to;
            c = d[i].w;
            if(e[b] > e[t] + c) {
                e[b] = e[t] + c;
                if(!inq[b]) {
                    q.push(b);
                    inq[b] ^= 1;
                }
            }
        }
        q.pop();
        inq[t] ^= 1;
    }
}

int main() {
    cin >> n >> m >> k;
    posc = revc = 0;
    memset(posd, 0x3f, sizeof(posd));
    memset(revd, 0x3f, sizeof(revd));
    memset(posh, -1, sizeof(posh));
    memset(revh, -1, sizeof(revh));
    for(int i = 0, a, b, c; i < m; i++) {
        cin >> a >> b >> c;
        addedge(pose, a, b, c, posc, posh);
        addedge(reve, b, a, c, revc, revh);
    }
    spfa(pose, posd, posh);
    spfa(reve, revd, revh);
    int x = 0;
    for(int i = 1, t; i <= n; i++) {
        t = posd[i] + revd[i];
        if(t > 10000) continue;
        if(x < t) x = t;
    }
    cout << x << endl;
    return 0;
}

 

CC BY-NC-SA 4.0 CodeVS 1992 – SPFA 图论基础模板 & 链式前向星 & STL by J. Chen is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.