spfa。。。。其实最好用floyed，最简单，只是很久没写spfa了，练习一下
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> using namespace std; int n , m , k , all; const int M = 1e5; int pre[M + 10] , other[M + 10] , last[M + 10] , cost[M + 10] , seq[M + 10]; int dis[M + 10] , Inque[M + 10]; void build(int x , int y , int z) { pre[++all] = last[x]; last[x] = all; other[all] = y; cost[all] = z; } int spfa(int s , int x) { memset(Inque , 0 , sizeof(Inque)); int head , tail , now , ed , dr; head = 1 , tail = 0; seq[++tail] = s; for(int i = 1 ; i <= n ; i++) dis[i] = 1 << 30; dis[s] = 0; Inque[s] = 1; while(head <= tail){ now = seq[head]; ed = last[now]; Inque[now] = 0; while(ed != -1){ dr = other[ed]; if(dis[now] + cost[ed] < dis[dr]){ dis[dr] = dis[now] + cost[ed]; if(!Inque[dr]){ Inque[dr] = 1; seq[++tail] = dr; } } ed = pre[ed]; } head++; } return dis[x]; } int main() { while(~scanf("%d %d %d",&n , &m , &k)){ memset(last , -1 , sizeof(last)); all = -1; for(int i = 1 ; i <= m ; i++){ int a , b , c; scanf("%d %d %d",&a , &b , &c); build(a , b , c); } int ans = 0; for(int i = 1 ; i <= n ; i++){ int tmp = 0; tmp += spfa(i,k); tmp += spfa(k,i); if(ans < tmp) ans = tmp; } printf("%d\n",ans); } return 0; }