#include <bits/stdc++.h>
using namespace std;
#define N 1010
#define PII pair<int, int>
vector<PII> G[N], G1[N];
int n, m, st, d1[N], v1[N], d2[N], v2[N];

void dij1() {
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(d1, 0x3f, sizeof(d1)); d1[st] = 0; memset(v1, 0, sizeof(v1));
    q.push({0, st});
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (v1[x]) continue; v1[x] = 1;
        for (auto i : G[x]) {
            int y = i.first, w = i.second;
            if (d1[y] > d1[x] + w) d1[y] = d1[x] + w, q.push({d1[y], y});
        }
    }
}

void dij2() {
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(d2, 0x3f, sizeof(d2)); d2[st] = 0; memset(v2, 0, sizeof(v2));
    q.push({0, st});
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (v2[x]) continue; v2[x] = 1;
        for (auto i : G1[x]) {
            int y = i.first, w = i.second;
            if (d2[y] > d2[x] + w) d2[y] = d2[x] + w, q.push({d2[y], y});
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &st);
    for (int i = 1, x, y, w; i <= m; i++) scanf("%d%d%d", &x, &y, &w), G[x].push_back({y, w}), G1[y].push_back({x, w});
    dij1(); dij2();
    int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, d1[i] + d2[i]);
    printf("%d", ans);
    return 0;
}

qkw代码：

#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define PII pair<int,int>
vector<PII>G[N],G1[N];
int n,m,st,d1[N],v1[N],d2[N],v2[N];
void dij1()
{
priority_queue<PII,vector<PII>,greater<PII>>q;
memset(d1,0x3f,sizeof(d1));d1[st]=0;memset(v1,0,sizeof(v1));
q.push({0,st});
while(!q.empty())
{
int x=q.top().second;q.pop();
if(v1[x])continue;v1[x]=1;
for(auto i:G[x])
{
int y=i.first,w=i.second;
if(d1[y]>d1[x]+w)d1[y]=d1[x]+w,q.push({d1[y],y});
}
}
}
void dij2()
{
priority_queue<PII,vector<PII>,greater<PII>>q;
memset(d2,0x3f,sizeof(d2));d2[st]=0;memset(v2,0,sizeof(v2));
q.push({0,st});
while(!q.empty())
{
int x=q.top().second;q.pop();
if(v2[x])continue;v2[x]=1;
for(auto i:G1[x])
{
int y=i.first,w=i.second;
if(d2[y]>d2[x]+w)d2[y]=d2[x]+w,q.push({d2[y],y});
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&st);
for(int i=1,x,y,w;i<=m;i++)scanf("%d%d%d",&x,&y,&w),G[x].push_back({y,w}),G1[y].push_back({x,w});
dij1();dij2();
int ans=0;for(int i=1;i<=n;i++)ans=max(ans,d1[i]+d2[i]);
printf("%d",ans);
return 0;
}