求来回最短路加起来最长的一条。
两次SPFA，然后选某个点的来回最长。（有向图）
Dijkstra+邻接矩阵 比较方便建立 反向图。
我用SPFA+2个邻接表（正图+反图），C++ 32ms。
#include #include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m,start; struct lx { int v,t; }; vector g1[1001]; vector g2[1001]; int dis1[1001]; int dis2[1001]; void SPFA(int *dis,vector g[]) { bool vis[1001]; queue q; for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=0; vis[start]=1,dis[start]=0; q.push(start); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int j=0;j dis[u]+t) { dis[v]=dis[u]+t; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { while(scanf("%d%d%d",&n,&m,&start)!=EOF) { for(int i=1;i<=n;i++) g1[i].clear(),g2[i].clear(); while(m--) { int u,v,t; scanf("%d%d%d",&u,&v,&t); lx now; now.v=v,now.t=t; g1[u].push_back(now); now.v=u; g2[v].push_back(now); } SPFA(dis1,g1); SPFA(dis2,g2); int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dis1[i]+dis2[i]); printf("%d\n",ans); } }