题目：
https://vjudge.net/problem/POJ-3268
题意：
找到一个点到ｘ的最短路和ｘ到这个点的最短路的和最大
先ｄｉｊ一次，把数据存下来，再矩阵转置，再ｄｉｊ一遍，求最大值
dijkstra的变形
两次ｄｉｊ，一次ｄｉｊ，翻转后再ｄｉｊ一次
代码：
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxm=1e5+3; const int inf=0x3f3f3f3f; int mmap[1003][1003],dis[1003],tt[1003],vis[1003]; int n,m; void dij(int s) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=inf; dis[s]=0; for(int i=1;i<n;i++) { int p=0,mmin=inf; for(int j=1;j<=n;j++) { if(!vis[j]&&dis[j]<mmin) { mmin=dis[j]; p=j; } } vis[p]=1; for(int j=1;j<=n;j++) { if(dis[j]>dis[p]+mmap[p][j]) { dis[j]=dis[p]+mmap[p][j]; } } } } void reve() { for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) swap(mmap[i][j],mmap[j][i]); } } int main() {int x; scanf("%d %d %d",&n,&m,&x); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) mmap[i][j]=0; else mmap[i][j]=inf; } } int u,v,w; for(int i=1;i<=m;i++) { scanf("%d %d %d",&u,&v,&w); mmap[u][v]=w; } dij(x); for(int i=1;i<=n;i++) tt[i]=dis[i]; reve(); dij(x); int ans=0; for(int i=1;i<=n;i++) { ans=max(ans,tt[i]+dis[i]); } printf("%d\n",ans); }
还有ｓｐｆａ的方法
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxm=1e5+3; const int inf=0x3f3f3f3f; int mmap[1003][1003],dis[1003],tt[1003],vis[1003]; int que[10000003]; int n,m,s; void spfa() { for(int i=1;i<=n;i++) dis[i]=inf; memset(vis,0,sizeof(vis)); dis[s]=0; int head=0,tail=1; que[head]=s; while(head<tail) { int u=que[head]; vis[u]=1; for(int j=1;j<=n;j++) { if(mmap[u][j]!=inf&&dis[j]>dis[u]+mmap[u][j]) { dis[j]=dis[u]+mmap[u][j]; if(!vis[j]) { vis[j]=1; que[tail]=j; tail++; } } } vis[u]=0; head++; } } void reve() { for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) swap(mmap[i][j],mmap[j][i]); } } int main() { scanf("%d %d %d",&n,&m,&s); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) mmap[i][j]=0; else mmap[i][j]=inf; } } int u,v,w; for(int i=1;i<=m;i++) { scanf("%d %d %d",&u,&v,&w); mmap[u][v]=w; } spfa(); for(int i=1;i<=n;i++) tt[i]=dis[i]; reve(); spfa(); int ans=0; for(int i=1;i<=n;i++) { ans=max(ans,tt[i]+dis[i]); } printf("%d\n",ans); }