【NOIP模拟】“新”的家园

题面

分析

题上悄悄的隐藏了一个，这是一个环的条件，这个一定得看出来。

就是这句话。所以不要把它当成基环树之类的了。。

前4个点，最短路随便跑吧。我还是不长教训用的spfa，人品太好，切勿效仿！！

后面的分，发现除了环上的边，其余多余的边其实很少，最多只有200条，意思是最多只有400个点间有边。

既然求最短路，何不把这200条边的图建出来，然后对于非环边跑floyd，再结合环上的边处理最短路。

我们可以找到离u和v最近的两个点,它们分别是u1,u2,v1,v1

无非这几种情况 u->v  u->u1->v1->v  u->u1->v2->v  u->u2->v1->v  u->u2->v2->v

代码是真不好写。。。

代码

  1. #include<bits/stdc++.h>  
  2. using namespace std;  
  3. #define M 404  
  4. #define N 500050  
  5. #define INF 0x3f3f3f3f  
  6. int n,m,Q,cnt,tot,mpn,tmpn;  
  7. int dis[M][M];  
  8. int d[N],vis[N],first[N],nt[N],eu[N],ev[N],ew[N],mp[N],tmp[N];  
  9. struct email  
  10. {  
  11.     int u,v,w;  
  12.     int nxt;  
  13. }e[N*4];  
  14. struct query  
  15. {  
  16.     int st,ed;  
  17. }a[N];  
  18. template<class T>  
  19. void read(T &x)  
  20. {  
  21.     x = 0;  
  22.     static char c = getchar();  
  23.     while(c < '0' || c > '9') c = getchar();  
  24.     while(c >= '0' && c <= '9')  
  25.     x = x * 10 + c - '0', c = getchar();  
  26. }  
  27. inline void add(int u,int v,int w)  
  28. {  
  29.     e[cnt].nxt=first[u];first[u]=cnt;  
  30.     e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;++cnt;  
  31. }  
  32. queue<int>q;  
  33. void spfa(int x)  
  34. {  
  35.     q.push(x);  
  36.     for(int i=1;i<=n;i++)d[i]=INF;  
  37.     d[x]=0;vis[x]=1;  
  38.     while(!q.empty())  
  39.     {  
  40.         int u=q.front();q.pop();vis[u]=0;  
  41.         for(int i=first[u];i;i=e[i].nxt)  
  42.         {  
  43.             int v=e[i].v,w=e[i].w;  
  44.             if(d[v]>d[u]+w)  
  45.             {  
  46.                 d[v]=d[u]+w;  
  47.                 if(!vis[v])  
  48.                 {q.push(v);vis[v]=1;}  
  49.             }  
  50.         }  
  51.     }  
  52. }  
  53. int cir(int u,int v)  
  54. {  
  55.     if(u==v)return 0;  
  56.     if(u>v)swap(u,v);  
  57.     v--;  
  58.     int x=nt[v]-(u?nt[u-1]:0);  
  59.     return min(x,nt[n-1]-x);  
  60. }  
  61.   
  62.   
  63. int main()  
  64. {  
  65.     read(n);read(m);read(Q);  
  66.     if(Q==1)  
  67.     {  
  68.         for(int i=1;i<=m;i++)  
  69.         {  
  70.             int u,v,w;  
  71.             read(u);u--;read(v);v--;read(w);  
  72.             add(u,v,w);add(v,u,w);  
  73.         }  
  74.         int s,t;  
  75.         read(s);s--;read(t);t--;  
  76.         spfa(s);printf("%d ",d[t]);  
  77.         return 0;  
  78.     }  
  79.     memset(nt,0x3f,sizeof(nt));  
  80.     for(int i=1;i<=m;i++)  
  81.     {  
  82.         int u,v,w;  
  83.         read(u);u--;read(v);v--;read(w);  
  84.         if(v==(u+1)%n)nt[u]=min(nt[u],w);  
  85.         else if(u==(v+1)%n)nt[v]=min(nt[v],w);  
  86.         else  
  87.         {  
  88.             eu[tot]=u,ev[tot]=v;ew[tot++]=w;  
  89.             tmp[tmpn++]=u,tmp[tmpn++]=v;          
  90.         }  
  91.     }  
  92.     for(int i=1;i<n;i++)nt[i]+=nt[i-1];  
  93.     sort(tmp,tmp+tmpn);  
  94.     mp[mpn++]=tmp[0];  
  95.     for(int i=1;i<tmpn;i++)  
  96.         if(tmp[i]!=tmp[i-1])  
  97.             mp[mpn++]=tmp[i];  
  98.     for(int i=0;i<mpn;i++)  
  99.         for(int j=0;j<mpn;j++)  
  100.             dis[i][j]=cir(mp[i],mp[j]);  
  101.     for(int i=0;i<tot;i++)  
  102.     {  
  103.         int u=lower_bound(mp,mp+mpn,eu[i])-mp;  
  104.         int v=lower_bound(mp,mp+mpn,ev[i])-mp;  
  105.         dis[u][v]=dis[v][u]=min(dis[u][v],ew[i]);  
  106.     }     
  107.     for(int k=0;k<mpn;k++)  
  108.         for(int i=0;i<mpn;i++)  
  109.             for(int j=0;j<mpn;j++)  
  110.                 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);             
  111.     for(int i=1;i<=Q;i++)  
  112.     {  
  113.         int u,v;  
  114.         read(u);u--;read(v);v--;  
  115.         int u1=(upper_bound(mp,mp+mpn,u)-mp)%mpn,u2=(u1-1+mpn)%mpn;  
  116.         int v1=(upper_bound(mp,mp+mpn,v)-mp)%mpn,v2=(v1-1+mpn)%mpn;  
  117.         int ans=cir(u,v);  
  118.         ans=min(ans,cir(u,mp[u1])+cir(mp[v1],v)+dis[u1][v1]);  
  119.         ans=min(ans,cir(u,mp[u1])+cir(mp[v2],v)+dis[u1][v2]);  
  120.         ans=min(ans,cir(u,mp[u2])+cir(mp[v1],v)+dis[u2][v1]);  
  121.         ans=min(ans,cir(u,mp[u2])+cir(mp[v2],v)+dis[u2][v2]);  
  122.         printf("%d ",ans);  
  123.     }  
  124.     return 0;  
  125. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/NSD-email0820/p/9841462.html