POJ 3411 Paid Roads

约定不等于承诺〃 2022-03-28 08:30 158阅读 0赞

[主题链接~~>][Link 1]

**做题情绪：**先前看过一次，感觉做多了状态压缩之后。再做这题就非常顺手了。

**解题思路： BFS + 状态压缩**

一个城市能够走多次，so ~ > 须要用状态压缩。開始用了优先队列可是后来发现不能够用。当中例子用优先队列就过不了，于是把标记数组改为记录达到某个城市达到某种 状态的最小花费，假设搜到某个状态花费比当前状态小。更新标记数组的花费。就继续搜下去。否则不向下搜，这样搜出全部的情况就能够了。

（注意推断的时候要推断终点城市是否在状态里，開始有点脑残了推断是否全部城市都到达了）。

**代码：**

#include<iostream>
    #include<sstream>
    #include<map>
    #include<cmath>
    #include<fstream>
    #include<queue>
    #include<vector>
    #include<sstream>
    #include<cstring>
    #include<cstdio>
    #include<stack>
    #include<bitset>
    #include<ctime>
    #include<string>
    #include<cctype>
    #include<iomanip>
    #include<algorithm>
    using namespace std  ;
    #define INT __int64
    #define L(x)  (x * 2)
    #define R(x)  (x * 2 + 1)
    const int INF = 0x3f3f3f3f ;
    const double esp = 0.0000000001 ;  // 问 mod  HDU 5063
    const double PI = acos(-1.0) ;
    const int mod = 1e9 + 7 ;
    const int MY = 10 + 5 ;
    const int MX = (1<<10) + 5 ;
    int n ,m ;
    int vis[MY][MX] ;
    struct node
    {
        int c1 ,c2 ;
    }mp[MY][MY][MY] ;
    struct NODE
    {
        int x ,cost ,key ;
    } ;
    int bfs(int x)
    {
        int ans = INF ;
        queue<NODE> q ;
        NODE curt ,next ;
        curt.x = x ;  // 终于到达的点
        curt.cost = 0 ;  // 花费
        curt.key = 1 ;  // 状态
        vis[0][1] = 0 ;
        q.push(curt) ;
        while(!q.empty())
        {
            curt = q.front() ;
            q.pop() ;
            if(curt.key &(1<<(n-1)))
                ans = min(ans ,curt.cost) ;
            for(int i = 0 ;i < n ; ++i)
              for(int j = 0 ;j < n ; ++j)
               if(mp[curt.x][i][j].c1 != -1)
               {
                  int costA = INF ,costB = INF ;
                  next.key  = curt.key ;
                  if(next.key&(1<<j)) // 预支点在里面
                       costA = curt.cost + mp[curt.x][i][j].c1 ; // 原先的花费加上当前花费
                  costB = curt.cost + mp[curt.x][i][j].c2 ;
                  next.cost = min(costA ,costB) ;
                  next.x = i ;
                  if(!(next.key&(1<<i)))
                         next.key |= (1<<i) ;
                  if(vis[i][next.key] > next.cost)
                  {
                      vis[i][next.key] = next.cost ;
                      q.push(next) ;
                  }
               }
        }
        return  ans ;
    }
    int main()
    {
        //freopen("input.txt" ,"r" ,stdin) ;
        int u ,v ,t ,c1 ,c2 ;
        while(~scanf("%d%d" ,&n ,&m))
        {
            memset(mp ,-1 ,sizeof(mp)) ;
            for(int S = 0 ;S < (1<<n) ; ++S)
              for(int i = 0 ;i < n ; ++i)
                 vis[i][S] = INF ;
            for(int i = 0 ;i < m ; ++i)
            {
                scanf("%d%d%d%d%d" ,&u ,&v ,&t ,&c1 ,&c2) ;
                u-- ; v-- ; t-- ;
                if(mp[u][v][t].c1 != -1)  // 防止重边（本题不知是否存在）
                        mp[u][v][t].c1 = min(mp[u][v][t].c1 ,c1) ;
                else    mp[u][v][t].c1 = c1 ;
                if(mp[u][v][t].c2 != -1)
                      mp[u][v][t].c2 = min(mp[u][v][t].c2 ,c2) ;
                else  mp[u][v][t].c2 = c2 ;
            }
            int mx = bfs(0) ;
            if(mx != INF)
                    cout<<mx<<endl ;
            else    cout<<"impossible"<<endl ;
        }
        return 0 ;
    }

[Link 1]: http://poj.org/problem?id=3411