道路与航线

解法一

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; 
   }

后话

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