北京人事考试网/网站的优化策略方案

传送门

题意: 找0到所有点中最短路的最长的一个

(可能会点达不到)

直接跑spfa

因为不会spfa 还提前了解了bellman-ford

/***
for( n )for(所有边)a->b a,b,w随便存边
dis[b] = min (dis[b],dis[a]+w)
松弛操作可以看出 bellman-ford 类似直接暴力循环n次之后一定满足
dis[b]<=dis[a]+w
三角不等式有负权边的问题
***/

/**
对bellman ford的
dis[b] =min(dis[b],dis[a]+w)
来做优化使用队列和打标记对 Bellman ford进行优化
但是其实看起来还是和dij差不多
**/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;const int N = 100010;int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}int spfa()
{memset(dist, 0x3f, sizeof dist);dist[0] = 0;queue<int> q;///存储待更新的点q.push(0);st[0] = true;///st存的是当前这个点是否在队列当中///存重复的点在队列当中是没有意义的while (q.size()){int t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i])///更新t的所有领边{int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j]){q.push(j);st[j] = true;}}}}return dist[n];
}int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof h);while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}int t = spfa();int maxn  = 0;int mp  =0;for(int i=n;i>=1;i--){if(dist[i]>=maxn)maxn =dist[i],mp=i;}cout<<maxn<<" "<<mp<<endl;return 0;
}