过路费【Floyd】

题目大意&＃xff1a;

思路&＃xff1a;
emm给你们讲一个故事&＃xff0c;FloydFloyd比SPFASPFA快。

啥&＃xff0c;不信&＃xff1f;那就随你喽。

某dalao的感人事迹&＃xff0c;上面是FloydFloyd&＃xff0c;下面是SPFASPFA。

这道题真的没想到是用FloydFloyd&＃xff0c;而且这题卡了我3小时。。。

哇我被Floyd卡了三小时我好菜啊

进入正题。

这道题用FloydFloyd的好处是&＃xff0c;FloydFloyd点排序后可以直接一边处理最短路&＃xff0c;一边可以处理最短路上点最大值。

所以&＃xff0c;我们要先将点按权值从小到大排一次序&＃xff0c;那么在num[i]num[i]&＃xff0c;num[j]num[j]&＃xff0c;num[k]num[k]中总有一个是最大值。

所以&＃xff0c;我们跑一边FloydFloyd,最短路和点权一起处理&＃xff0c;就可以求出真正的最短路了。

代码&＃xff1a;

#include
#include
#include
#include
using namespace std;int n,m,x,y,z,t,d[501][501],dis[501][501],o[501];
int num[501],ak[501];bool cmp(int x,int y)
{return num[x]}void fre()
{freopen("toll.in","r",stdin);freopen("toll.out","w",stdout);
}int main()
{fre();scanf("%d%d%d",&n,&m,&t);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d",&num[i]);ak[i]&＃61;i;} memset(d,127/3,sizeof(d));memset(dis,127/3,sizeof(dis)); //初始化for (int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%d%d%d",&x,&y,&z);d[x][y]&＃61;d[y][x]&＃61;min(d[x][y],z);} sort(ak&＃43;1,ak&＃43;1&＃43;n,cmp); //按点权排序for (int kk&＃61;1;kk<&＃61;n;kk&＃43;&＃43;) //Floyd{int k&＃61;ak[kk];for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for (int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){if (i!&＃61;j&&j!&＃61;k&&k!&＃61;i){d[i][j]&＃61;min(d[i][j],d[i][k]&＃43;d[k][j]); //求最短路dis[i][j]&＃61;min(dis[i][j],d[i][j]&＃43;max(num[i],max(num[j],num[k]))); //求加点权的最短路}}}} //初始化结束for (int i&＃61;1;i<&＃61;t;i&＃43;&＃43;) //O(1)输出{scanf("%d%d",&x,&y);printf("%d\n",dis[x][y]);}return 0;
}