• 解法一

    1. 看数据范围,以及一点分析,能够确定这是单源最短路,可选DJ与SPFA,但是图中存有负权边,只能SPFA了。

      However

      图片说明

      so,这里要用一个江湖人称“SLF”的优化,即当前节点到起点距离小于队首的时候,将此点插入队首,否则,正常插入队尾。感觉这种优化可能被用到的机会很少,但很可能正好解决掉了专门卡spfa的数据以及网格图。

    2. 解法一代码

      #include<deque>
      #include<algorithm>
      #include<cstring>
      #include<string>
      #include<cstdio>
      using namespace std;
      const int N=4e5+10;
      int n,m1,m2,s,tot;
      int h[N],nex[N],ver[N],pri[N],vis[N],dis[N];
      inline void add(int x,int y,int z)
      {
      nex[tot]=h[x];
      ver[tot]=y;
      pri[tot]=z;
      h[x]=tot++;
      }
      inline void spfa(int s)
      {
      memset(dis,0x3f,sizeof(dis));
      memset(vis,0,sizeof(vis));
      deque<int>q;
      dis[s]=0;vis[s]=1;
      q.push_back(s);
      while(q.size())
      {
       int now=q.front();q.pop_front();
       vis[now]=0;
       for (int i=h[now];~i;i=nex[i])
       {
           int j=ver[i];
           if(dis[j]>dis[now]+pri[i])
           {
               dis[j]=dis[now]+pri[i];
               if(!vis[j])
               {
                   vis[j]=1;
                   if(q.size()&&dis[j]<dis[q.front()]) q.push_front(j);
                   else q.push_back(j);
               }
           }
       }
      }
      }
      int main()
      {
      memset(h,-1,sizeof(h));
      scanf("%d%d%d%d",&n,&m1,&m2,&s);
      for (int i=1;i<=m1;i++)
      {
       int x,y,z;
       scanf("%d%d%d",&x,&y,&z);
       add(x,y,z),add(y,x,z);
      }
      for (int i=1;i<=m2;i++)
      {
       int x,y,z;
       scanf("%d%d%d",&x,&y,&z);
       add(x,y,z);
      }
      spfa(s);
      for (int i=1;i<=n;i++)
      {
       if(dis[i]==0x3f3f3f3f) puts("NO PATH");
       else printf("%d\n",dis[i]);
      }
      return 0;
      }
  • 解法二

    1. 注意到道路权值为正,航线权值为负,且有向边不会构成一个环,那么可以根据拓扑排序的思想,把每一个有道路连接的小镇归为一个连通块,然后在每一个联通块中连边,就能构成一个有向连通图,然后能在规定时间内跑出单源最短路,比解法一更快

    2. 解法二代码

      #include<bits/stdc++.h>
      using namespace std;
      const int N=3e4+10,M=2e5+10;
      int n,m1,m2,s,num,dfn;
      int h[N],bel[N],deg[N],dis[N];
      bool vis[N];
      struct nk
      {
      int val,pos;
      bool operator < (const nk &b)const
      {
       return val>b.val;
      }
      };
      struct E {int nex,to,dis;}e[M];
      vector<int>c[N];
      queue<int>q;
      inline void add(int u,int v,int w)
      {
      e[++num].nex=h[u];
      e[num].to=v;
      e[num].dis=w;
      h[u]=num;
      }
      inline void dfs(int x)
      {
      bel[x]=dfn,vis[x]=1;
      c[dfn].push_back(x);
      for(int i=h[x];i;i=e[i].nex)
      {
       int j=e[i].to;
       if(vis[j]) continue;
      
       dfs(j);
      }
      }
      inline void dj(int id)
      {
      priority_queue<nk>p;
      int len=c[id].size();
      for(int i=0;i<len;i++)
       p.push((nk){dis[c[id][i]],c[id][i]});
      while(p.size())
      {
       int now=p.top().pos;p.pop();
      
       if(vis[now]) continue;
       vis[now]=1;
       for(int i=h[now];i;i=e[i].nex)
       {
           int j=e[i].to,w=e[i].dis;
           if(dis[now]+w<dis[j])
           {
               dis[j]=dis[now]+w;
               if(bel[now]==bel[j]) p.push((nk){dis[j],j});
           }
           deg[bel[j]]--;
           if(!deg[bel[j]]&&bel[now]!=bel[j]) q.push(bel[j]);
       }
      }
      }
      int main()
      {
      scanf("%d%d%d%d",&n,&m1,&m2,&s);
      for (int i=1;i<=m1;i++)
      {
       int x,y,z;scanf("%d%d%d",&x,&y,&z);
       add(x,y,z),add(y,x,z);
      }
      //道路
      for (int i=1;i<=n;i++)
       if(!vis[i]) ++dfn,dfs(i);
      //划分一个连通块 
      for (int i=1;i<=m2;i++)
      {
       int x,y,z;
       scanf("%d%d%d",&x,&y,&z);
       add(x,y,z);deg[bel[y]]++;
      }
      //航线 
      memset(vis,0,sizeof(vis));
      memset(dis,0x3f,sizeof(dis));
      dis[s]=0,q.push(bel[s]);
      for(int i=1;i<=dfn;i++) if(!deg[i]) q.push(i);
      while(q.size())
      {
       int now=q.front();
       q.pop();dj(now);
      }
      for (int i=1;i<=n;i++)
      {
       if(dis[i]>=1e9) printf("NO PATH\n");
       else printf("%d\n",dis[i]);
      }
      return 0; 
      }
  • 后话

    好像不太会用格式。如果对内容或是格式有些许不适,还请指出(^▽^)