Elaxia 的路线——抛弃Dijkstra 吧

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<vector>
 5 #include<cstdio>
 6 #include<queue>
 7 using namespace std;
 8 const int N=2048,INF=0x3f3f3f3f;
 9 int res,n,m,sx,sy,tx,ty;
10 int d1[N],d2[N],d3[N],d4[N];
11 vector<int> gr[N],dis[N];
12 bool check(int x){return d1[x]+d2[x]==d1[sy]&&d3[x]+d4[x]==d3[ty];}
13 int spfa(int sp,int d[N]){
14     bool vis[N];
15     queue<int> q;
16     memset(vis,0,sizeof vis);
17     
18     d[sp]=0;vis[sp]=true;
19     q.push(sp);
20     while(!q.empty()){
21         int x=q.front();q.pop();
22         vis[x]=false;
23         for(int i=0;i<gr[x].size();i++)
24             if(d[gr[x][i]]>d[x]+dis[x][i]){
25                 d[gr[x][i]]=d[x]+dis[x][i];
26                 if(!vis[gr[x][i]])q.push(gr[x][i]),vis[gr[x][i]]=true;
27             }
28     }
29 }
30 int main(){
31     memset(d1,0x3f,sizeof d1);memset(d2,0x3f,sizeof d2);
32     memset(d3,0x3f,sizeof d3);memset(d4,0x3f,sizeof d4);
33     
34     cin>>n>>m>>sx>>sy>>tx>>ty;
35     for(int i=1;i<=m;i++){
36         int x,y,v;scanf("%d%d%d",&x,&y,&v);
37         gr[x].push_back(y);dis[x].push_back(v);
38         gr[y].push_back(x);dis[y].push_back(v);
39     }
40     
41     spfa(sx,d1);spfa(sy,d2);
42     spfa(tx,d3);spfa(ty,d4);
43     
44     for(int i=1;i<=n;i++)
45         if(check(i))
46             for(int j=i+1;j<=n;j++)
47                 if(check(j))
48                     res=max(res,abs(d1[i]-d1[j]));
49     cout<<res<<endl;
50     return 0;
51 }