Sicily 1700. Ping

Sicily 1700. Ping

训练的题目

最短路变形

题意:这个题意,太长了,总结回来只有两三句话。输入n表示n个点,从0到n-1,输入m表示m条无向边,输入t,表示终点。要你求起点0到终点t的最短路,不过要先满足一个条件,就是路径的点数不超过10个(包括起点和终点在内 <= 10),如果在10个点内娶不到或者图根本不连通,那么输出no,否则输出最短路

又是一个加了限制的最短路,是要先满足10个点以内再求最短路的,训练的时候就是看错了一直WA。

这题和   poj 1724 ROADS  是一样的题目。可以看作每条边的花费是1点数,你从0出发,手上有9点数,在点数够用的情况下走到终点t的最短路

因此仿照poj这题的代码,写了一个dp,就过了,再仿照写了个bfs搜索,也过了 , 在仿照写了个优先队列+dij , 得到一个MLE,这个是为什么?其实还没想清楚,应该是入队的元素太多(没有加以限制)导致爆了空间,poj那题是100个点,给了64m,这题是1000个点,给了32m,应该是这样了

 

后来上网找到了唯一一个代码,作者的代码写得比我好啊,简单,易懂,附上地址  

http://soj.me/viewsource.php?sid=1796545

 

1.dp的代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
const int lim = 9;

typedef pair<int,int>pii;
vector<pii>e[N];
int d[N][15];

void dfs(int u , int c)
{
   if(d[u][c] != -1) return ;
   d[u][c] = INF;
   int size = e[u].size();
   for(int i=0; i<size; i++)
   {
      pii temp = e[u][i];
      int v = temp.first;
      int w = temp.second;
      if(c-1 >= 0)
      {
         dfs(v,c-1);
         if(d[v][c-1] + w < d[u][c])
            d[u][c] = d[v][c-1] + w;
      }
   }
}

int main()
{
   int n,m,t;
   while(scanf("%d%d%d",&n,&m,&t)!=EOF && n)
   {
      for(int i=0; i<n; i++) e[i].clear();
      while(m--)
      {
         int u,v,w;
         scanf("%d%d%d",&u,&v,&w);
         e[u].push_back( make_pair(v,w) );
         e[v].push_back( make_pair(u,w) );
      }

      memset(d,-1,sizeof(d));
      for(int i=0; i<=lim; i++) d[0][i] = 0;
      int res = INF;
      for(int i=0; i<=lim; i++)
      {
         dfs(t,i);
         if(d[t][i] < res) res = d[t][i];
      }
      if(res == INF) printf("no\n");
      else           printf("%d\n",res);
   }
   return 0;
}

 

 

2.bfs搜索,彻底搜索更新所有状态

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
const int lim = 9;

typedef pair<int,int>pii;
vector<pii>e[N];
int d[N][15];

void bfs(int s , int t)
{
   bool inq[N];
   queue<int>q;
   while(!q.empty()) q.pop();
   memset(inq,false,sizeof(inq));
   memset(d,0x3f,sizeof(d));
   for(int i=0; i<=lim; i++) d[s][i]=0;
   inq[s] = true;
   q.push(s);

   while(!q.empty())
   {
      int u = q.front();
      q.pop();
      inq[u] = false;
      int size = e[u].size();
      for(int i=0; i<size; i++)
      {
         pii temp = e[u][i];
         int v = temp.first;
         int w = temp.second;
         int c = 1;
         for(int j=1; j<=lim; j++)
            if(d[u][j-c] + w < d[v][j])
            {
               d[v][j] = d[u][j-c] + w;
               if(!inq[v])
               {
                  inq[v] = true;
                  q.push(v);
               }
            }
      }
   }

   int res = INF;
   for(int i=0; i<=lim; i++)
      if(d[t][i] < res)
         res = d[t][i];
   if(res == INF) printf("no\n");
   else           printf("%d\n",res);
}

int main()
{
   int n,m,t;
   while(scanf("%d%d%d",&n,&m,&t)!=EOF && n)
   {
      for(int i=0; i<n; i++) e[i].clear();
      while(m--)
      {
         int u,v,w;
         scanf("%d%d%d",&u,&v,&w);
         e[u].push_back( make_pair(v,w) );
         e[v].push_back( make_pair(u,w) );
      }
      bfs(0,t);
   }
}

 

3.网上找到的代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
const int lim = 9;

typedef pair<int,int>pii;
vector<pii>e[N];
int d[N];
int len[N];

void bfs(int s , int t)
{
   bool inq[N];
   queue<int>q;
   while(!q.empty()) q.pop();
   memset(inq,false,sizeof(inq));
   memset(d,0x3f,sizeof(d));
   memset(len,0,sizeof(len));
   d[s] = 0;
   inq[s] = true;
   q.push(s);

   while(!q.empty())
   {
      int u =q.front();
      q.pop();
      inq[u] = false;
      int size = e[u].size();
      for(int i=0; i<size; i++)
      {
         pii temp = e[u][i];
         int v = temp.first;
         int w = temp.second;
         int c = 1;
         if(d[u] + w < d[v])
         {
            d[v] = d[u] + w;
            len[v] = len[u] + c;
            if(len[v] <= lim) q.push(v);
         }
      }
   }

   if(d[t] == INF) printf("no\n");
   else            printf("%d\n",d[t]);
}

int main()
{
   int n,m,t;
   while(scanf("%d%d%d",&n,&m,&t)!=EOF && n)
   {
      for(int i=0; i<n; i++) e[i].clear();
      while(m--)
      {
         int u,v,w;
         scanf("%d%d%d",&u,&v,&w);
         e[u].push_back( make_pair(v,w) );
         e[v].push_back( make_pair(u,w) );
      }
      bfs(0,t);
   }
}

 

转载于:https://www.cnblogs.com/scau20110726/archive/2013/04/30/3052358.html

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

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

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

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

(0)


相关推荐

  • s3c2440时钟频率「建议收藏」

    s3c2440时钟频率「建议收藏」分类:LINUX++++++++++++++++++++++++++++++++++++++++++本文系本站原创,欢迎转载!转载请注明出处:http://blog.csdn.net/mr_raptor/article/details/6555734++++++++++++++++++++++++++++++++++++++++++系统时钟MINI2440开发板

  • eclipse如何导入java文件_xml表格

    eclipse如何导入java文件_xml表格代码快速实现xml转换为Excel(xml转excel通用类-java-完成代码可作工具使用)用代码实现xml文件/数据转换为excel文件。(java)—-何潮背景:最近项目要做导出功能,但导出的数据对象类型实在太多了,一个个去实现;实在是没心情去做。于是———-意义:快速实现数据导出为什么是xmltoexcel?因为项目中可以直接使用xml数据。所以就选择xm…

  • Python安装第三方库(离线+在线)「建议收藏」

    Python安装第三方库(离线+在线)「建议收藏」一、离线安装以安装resquest包为例1、检查依赖模块的依赖包检查:在CMD命令窗口中输入pipshowrequests如图所示,依赖的包包括certifi,idna,urllib3,chardet可以在https://www.lfd.uci.edu/~gohlke/pythonlibs/网站下载对应的安装程序(Ctrl+F可以在页面查找所需安装包)certifi-2019.9.11-py2.py3-none-any.whlchardet-3.0.4-py2.py3-none-an

  • 版权文字:Power by DedeCms 如何去除?[通俗易懂]

    版权文字:Power by DedeCms 如何去除?[通俗易懂]dedeCMS系统中的版权声明信息中含有“PowerbyDedeCms”字样,如何去除?dedeCMS近期的新版本至2013-6-7更新包以来,不管新版还是旧版更新补丁包,更新后网站页底都会出现powerbydedecms。*一、powerbydedecms什么意思?在我们上网的时候,会见到页面页底很多带powerbydedecms的网站,powerbydede…

  • 在目录下打开命令行_如何用命令行打开文件夹

    在目录下打开命令行_如何用命令行打开文件夹用命令行打开指定目录。基本指令nautilus+路径命令可以在ubuntu上直接打开此路径的目录。如nautilus~/workspace/。打开win格式的路径在Windows上的路径为反斜线\,在ubuntu命令行是无法识别的,此时需要将\转换为/。使用sed命令可以自动转换。以下命令可以打开/home/eric.cai/Workspace/目录:nautilus$(echo’\home\eric.cai\Workspace’|sed‘s+\\+/+g’)写成

    2022年10月15日
  • 诛仙3 私服架设 仿官网「建议收藏」

    诛仙3 私服架设 仿官网「建议收藏」背景:想情怀一把,抑或想怀旧一下,利用官网的乐趣+私服的金钱,打造一个全新的玩法,这就是我的追求。当然了,好东西是要分享的。 全套工具在百度云盘中: 链接:http://pan.baidu.com/s/1i5HG9YP密码:zg7i…

发表回复

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

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