POJ 3411 Paid Roads

POJ 3411 Paid Roads

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

主题链接~~>

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

解题思路:  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 ;
}

版权声明:本文博客原创文章。博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117176.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 爱,该放弃吗_有一种爱叫做放手

    爱,该放弃吗_有一种爱叫做放手爱,绝不是缺了就找,更不是累了就换。   找一个能一起吃苦的,而不是一起享受的   找一个能一起承担的,而不是一起逃避的   找一个能对你负责的,而不是对爱情负责的   爱情是盲目的,生活是现实的   因为爱情只不过是人类为了逃避现实而衍生的产品   为了逃避现实,我寻找爱情   为了寻找爱情,我失去真情   失去了真情,才发现早已身陷虚情.   你以为爱情是什么?   一点点的动心,一点点的冲动

  • Runnable 和Callable的实现与区别,应用场景

    Java提供了三种创建线程的方法1:通过实现Runnable接口2:通过继承Thread接口3:通过Callable和Future创建线程相同点都是接口都可以编写多线程程序都采用Thread.start()启动线程不同点(1)Callable规定的方法是call(),Runnable规定的方法是run()。其中Runnable可以提交给Thread来包装下,直接启动一个…

  • 《哈佛大学公开课:幸福课》 学习笔记(1)

    《哈佛大学公开课:幸福课》 学习笔记(1)视频链接:http://v.163.com/special/sp/positivepsychology.html当初《幸福课》在网易公开课很火,当然现在也很火。但是由于对门户热门内容的成见,再加上一个江湖骗子式的课程名字,我还以为是又一个简单空洞的心灵鸡汤。但是今天看完了第一节课,事实告诉我,真是要相信群众的眼睛呀,而且随便怀疑哈佛出品也未免太过自信。70+分钟的时间内,没有多少废话,反复

  • 用burpsuite抓包,谷歌 / 火狐浏览器 该怎么设置BurpSuite代理?——超详细教程——CTF Web小白入门基础篇

    用burpsuite抓包,谷歌 / 火狐浏览器 该怎么设置BurpSuite代理?——超详细教程——CTF Web小白入门基础篇以下是我自己操作过的,理一理思路。使用BurpSuite的套路是:浏览器设置BurpSuite代理——>BurpSuite调至on状态——>访问web程序——>进行抓包分析下面以火狐和谷歌两个例子分开讲:一、谷歌:首先burpsuite设置:然后:1.下载插件:chrome://extensions2.(与burp一致)3.可以使用了4.不出意外…

  • 安卓ExpandableListView的详细使用教程(附代码解析过程)[通俗易懂]

    安卓ExpandableListView的详细使用教程(附代码解析过程)[通俗易懂]ExpandableListView又称可扩展的ListView,它可以实现点击父项展开子项的效果,本文实现了一个比较精美的ExpandableListView。

  • ExtJs自学教程(1):一切从API開始

    ExtJs自学教程(1):一切从API開始

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号