记录编号	554570	评测结果	AAAAAAAAAA
题目名称	聚会	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-09-15 21:00:15	内存使用	0.00 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define max(x,y) (x) > (y) ? (x) : (y)
#define min(x,y) (x) < (y) ? (x) : (y)
#define INF 0x3f3f3f3f

using namespace std;
const int maxN = 1e3 + 10;

struct road{
    int w,nxt;
}; 

void SPFA(int s,int *dis,vector<road> *g);

vector <road> g1[maxN];
vector <road> g2[maxN];
int diss[2][maxN],vis[maxN],pre[maxN];
int n,m,x;
int main(void){
    freopen("partyb.in","r",stdin);
    freopen("partyb.out","w",stdout);
    scanf("%d%d%d",&n,&m,&x);
    for (int i = 1;i <= m;i ++){
        int a,b,t;
        scanf("%d%d%d",&a,&b,&t);
        bool lol = false;
        for (int j = 0;j < g1[a].size();j ++){
            if (g1[a][j].nxt == b){
                g1[a][j].w = min(g1[a][j].w,t);
                lol = true;
            }
        }
        for (int j = 0;j < g2[b].size();j ++){
            if (g2[b][j].nxt == a){
                g2[b][j].w = min(g2[b][j].w,t);
                lol = true;
            }
        }
        if (lol)
            continue;
        road e;
        e.nxt = b,e.w = t;
        g1[a].push_back(e);
        e.nxt = a,e.w = t;
        g2[b].push_back(e);
    }
    SPFA(x,diss[0],g1);
    SPFA(x,diss[1],g2);
    int ans = 0;
    for (int i = 1;i <= n;i ++){
        if (diss[0][i] + diss[1][i] < INF)
           ans = max(ans,diss[0][i] + diss[1][i]);
    }
    printf("%d\n",ans);
    return 0;
}

void SPFA(int s,int *dis,vector<road> *g){
    memset(dis,0x3f,sizeof(int) * maxN);
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    dis[s] = 0;
    queue <int> q;
    q.push(s);
    vis[s] = 1;
    while (!q.empty()){
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = 0;i < g[x].size();i ++){
            int y = g[x][i].nxt,w = g[x][i].w;
            if (dis[y] > dis[x] + w){
                dis[y] = dis[x] + w;
                pre[y] = x;
                if (!vis[y])
                   q.push(y),vis[y] = 1;
            }
        }
    }
}