蒟蒻刚学 Dijkstra
(是根据一位初一就 AK 了 NOIP-PJ2018 的神仙的博客学的)
什么堆之类的优化都不会
(其实我连 queue 也不会用)
只好写一个不带任何优化的双向 Dijkstra
不过只要吸氧就能过
- Code
- #pragma GCC optimize(2)
- // 手动 O2 优化
- #include<bits/stdc++.h>
- using namespace std;
- const long long inf = 2147483647;
- long long dis[2000];
- long long ans[2000];// 代表每个点的最短路径 (去 + 回)
- int eh[2000] = {0};// 邻接表
- bool used[2000] = {0};// 代表这个点的最短路径是否确定
- struct EE{
- int st,val,ne;
- }edge[200000];// 结构体存边
- int n,m,s,nw;
- long long minn;
- inline void Read(){
- scanf("%d%d%d",&n,&m,&s);
- for(int i = 1;i<=m;i++){
- int x;
- scanf("%d%d%d",&x,&edge[i].st,&edge[i].val);
- edge[i].ne = eh[x];
- eh[x] = i; // 存入邻接表
- }
- }
- void findmin(){
- for(int i = 1;i<=n;i++){
- if(!used[i]&&minn>dis[i]){
- minn = dis[i];
- nw = i;
- }
- }
- }
- inline void dijkstra1(){ // 单源最短路径
- if(used[nw])return;
- used[nw] = 1;
- for(int i = eh[nw];i!=0;i = edge[i].ne)
- if(!used[edge[i].st])dis[edge[i].st] = min(dis[edge[i].st],dis[nw]+edge[i].val);//dijkstra 基本操作
- minn = inf;
- findmin(); // 寻找剩下点中原点到这个点最短路径最短的
- dijkstra1();
- }
- inline void dijkstra2(){ // 单终点最短路径
- used[nw] = 1;
- if(used[s])return;// 如果到终点的最短路径确定下来就停止
- for(int i = eh[nw];i!=0;i = edge[i].ne)
- if(!used[edge[i].st])dis[edge[i].st] = min(dis[edge[i].st],dis[nw]+edge[i].val);
- minn = inf;
- findmin();
- dijkstra2();
- }
- inline void Print(){// 输出, 找出最长的最短路径
- long long c = -1;
- for(int i= 1;i<=n;i++)if(ans[i]>c) c = ans[i];
- printf("%lld",c);
- }
- int main(){
- Read();
- for(int i = 1;i<=n;i++)dis[i] = inf;
- for(int i = 1;i<=n;i++){
- dis[i] = 0;
- nw = i;
- dijkstra2();
- memset(used,0,sizeof(used));
- ans[i] += dis[s];
- for(int i = 1;i<=n;i++)dis[i] = inf;
- } // 第一次 Dijkstra(去)
- nw = s;
- dis[s] = 0;
- dijkstra1();// 第二次 Dijkstra(回)
- for(int i = 1;i<=n;i++)ans[i]+=dis[i];
- Print();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2947928.html