【NOIP2012模拟8.7】找位置(暴力全排列)-白红宇

【NOIP2012模拟8.7】找位置(暴力全排列)

阅读量：220 次

发布时间：2019-03-01

本文共 1302 字，大约阅读时间需要 4 分钟。

思路:K比较小，暴力预处理K次最短路不必说。问题在于哪种排列是最优的呢？采用全排列暴力，每种顺序按照一个环走一遍。

至于一条路走两遍以及以上的情况，在起点的枚举中会被包括进去。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define debug(a) cout<<#a<<"="<
            <
             
              P;///first最短距离,second顶点的编号struct edge{ LL to,cost;};struct SHOP{ LL id,pos;}shop[10];bool cmp(SHOP A,SHOP B){ return A.pos
              
               
                g[maxn];LL vis[maxn];LL dis[maxn][10];LL n,m;void dijkstra(LL st,LL k){ LL s=st;///起点是st dis[s][k]=0; memset(vis,0,sizeof(vis));///初始化 priority_queue< P, vector
                 , greater
                 >que; que.push({0,s}); while(!que.empty()) { P p=que.top();que.pop(); int v=p.second; if(vis[v]) continue; vis[v]=1; for(int i=0;i
                 
                  dis[v][k]+e.cost) { dis[e.to][k]=dis[v][k]+e.cost; que.push({dis[e.to][k],e.to}); } } }}int main(void){ memset(dis,0x3f,sizeof(dis));///初始化 LL n,m,k;n=read();m=read();k=read(); for(LL i=1;i<=k;i++){ shop[i].id=read(); shop[i].pos=i; } for(LL i=1;i<=m;i++){ LL u,v,cost;u=read();v=read();cost=read(); g[u].push_back({v,cost}); g[v].push_back({u,cost}); } for(LL i=1;i<=k;i++){ dijkstra(shop[i].id,shop[i].pos); } LL ans=0x3f3f3f3f3f3f3f3f; for(LL i=1;i<=n;i++){ bool flag=1; for(LL j=1;j<=k;j++){ if(shop[j].id==i){ flag=0; } } if(flag==0) continue; do{ LL sum=0; /// for(LL j=1;j<=k;j++) cout<
                  
                   <<" "; /// cout<