哈理工 oj 2122 旅行(map + 最短路dij算法)

哈理工 oj 2122 旅行(map + 最短路dij算法)旅行TimeLimit:1000MSMemoryLimit:32768KTotalSubmit:18(6users)TotalAccepted:3(3users)Rating:SpecialJudge:NoDescription“04.24,和Sakur

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

旅行
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 18(6 users) Total Accepted: 3(3 users) Rating: 哈理工 oj 2122 旅行(map + 最短路dij算法)哈理工 oj 2122 旅行(map + 最短路dij算法)哈理工 oj 2122 旅行(map + 最短路dij算法)哈理工 oj 2122 旅行(map + 最短路dij算法) Special Judge: No
Description

04.24,和Sakura去东京天空树,世界上最暖和的地方天空树的顶上。”

04.26,和Sakura去明治神宫,有人在那里举办婚礼。”

04.25,和Sakura去迪士尼,鬼屋很可怕,但是有Sakura在,所以不可怕。”

Sakura最好了。”

                                    ——江南 《龙族》

 

绘梨衣和路明非今天要从迪士尼前往天空树,但他们的钱不多了,所以能省则省,他们现在有一个地图上面有n个景点和m条景点之间的路,每条路坐车都需要一定的钱数,现在他们求助于你,请你帮他们计算下从当前地点到目的地最少需要的钱数。

Input

有多组数据,每组数据第一行有两个数字2<=n<=300001<=m<=30000

接下来n行输入n个地名。

接下来m行每行有两个字符串(长度不超过20)和一个数字,代表两地之间的坐车的费用。

接下来一行输入两个字符串分别代表起点和终点。

Output

一个int数代表最少需要的钱数。

数据保证不会超过int型范围。

Sample Input
2 1
disney
TokyoSkyTree
disney TokyoSkyTree 1
disney TokyoSkyTree
Sample Output
1
Source

2014暑假集训练习赛(7月19日)

看到 理工题目上 这个题目做的人没几个  ,就看看是什么玩意儿~!~

#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<cctype>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int maxn=30003;
const int INF=0x1f1f1f1f;
int n,m;
//标记起始位置
string s;
string e;
map<string,int>cnt;//映射成节点编号

struct Edge
{
    int from,to,dist;
    Edge(int u,int v,int d):from(u),to(v),dist(d) {}
};
vector<Edge>edges;//存储边的结点信息
vector<int>G[maxn];//邻接表
bool done[maxn];   //标记是否访问过
int d[maxn];    //距离数组
struct heapnode //用于优先队列自定义
{
    int d,u;
    bool operator <(const heapnode rhs) const
    {
        return d > rhs.d;
    }
    heapnode(int dd,int uu):d(dd),u(uu) {}
};


void init()//初始化必不可少
{
    for(int i=0; i<n; i++)
        G[i].clear();
    edges.clear();
}

void addedge(int from,int to,int dist)
{
    edges.push_back(Edge(from,to,dist));
    int m = edges.size();
    G[from].push_back(m-1);
}

void dij( int s)
{
    priority_queue<heapnode>Q;
    for(int i=0; i<=n; i++)//初始化距离数组
        d[i]=INF;
    d[s]=0;
    memset(done ,0,sizeof(done));
    Q.push( heapnode(0,s) );
    while(!Q.empty())
    {
        heapnode x = Q.top();
        Q.pop();
        int u=x.u;
        if(u==cnt[e])
        {
            printf("%d\n",x.d);
            break;
        }
        if(done[u])continue;
        done[u] = true;
        for(int i=0; i<G[u].size(); i++)
        {
            Edge& e=edges[G[u][i]];//取出来一条邻接边
            if(d[e.to]>d[u]+e.dist)
            {
                d[e.to] = d[u] + e.dist;
                Q.push((heapnode(d[e.to],e.to)));
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int t=1;
        int ans=0;
        string str;
        init();
        for(int i=0; i<n; i++)
        {
            cin>>str;
            cnt[str]=t++;
        }
        for(int i=0; i<m; i++)
        {
            string str2;
            int x;
            cin>>str>>str2>>x;
            addedge(cnt[str],cnt[str2],x);
            addedge(cnt[str2],cnt[str],x);
        }
        cin>>s>>e;
        dij(cnt[s]);
        s.clear();
        e.clear();
        cnt.clear();
    }
    return 0;
}
/*
2 1
a
v
a v 1
a v
3 2
a
b
c
a b 2
b c 3
a c
*/

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

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

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

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

(0)
blank

相关推荐

  • 通过Java实现求水仙花数「建议收藏」

    通过Java实现求水仙花数「建议收藏」用户输入一个数,判断是否是”水仙花数”,所谓”水仙花数”是指一个三位数,其各位数字立方和等于该数本身。例如:153是一个”水仙花数”,因为153=1的三次方+5的三次方+3的三次方。程序同用户交互是通过Scanner来实现的,jdk中封装了一个类Scanner,该类的职责就是接收键盘的输入值,并保存到程序的变量中,体现了程序和用户的交互功能,适合新手学习。

  • android之实现打开相册、拍照录像、播放视频、保存图片到系统相册\指定位置、图片压缩[通俗易懂]

    android之实现打开相册、拍照录像、播放视频、保存图片到系统相册\指定位置、图片压缩[通俗易懂]———照相录像——//实现照相、录像的功能publicvoidcameraForphoto(){Intentintent=newIntent(MediaStore.ACTION_IMAGE_CAPTURE);Filefile=newFile(Environment.getExternalStorageDirecto…

  • 这2个PDF转Word免费不限页数工具很多人没用过

    这2个PDF转Word免费不限页数工具很多人没用过很多人在搜索下载过PDF转换器的小伙伴都会有一个灵魂拷问:难道就没有免费还没页数限制的PDF转Word的工具吗?小编经过不断的对比和试用,找到以下两款好用免费的工具,相信总有一个你能用上。一、PDF转换器相信了解PDF这种文档格式设计由来的人对于Adobe肯定不陌生,所以首先要说的PDF转换工具就是AdobePDF,下载安装后打开软件,直接将PDF拖到软件页面打开即可,然后点击左上角“文件”中的“另存为其他”,选择我们需要转换成的Word格式就可以了。或者点击右侧“工具”选项中的“将文件导出为”并

  • vue-router传递参数的几种方式

    vue-router传递参数的几种方式vue-router传递参数分为两大类编程式的导航router.push声明式的导航&lt;router-link&gt;编程式的导航router.push编程式导航传递参数有两种类型:字符串、对象。字符串字符串的方式是直接将路由地址以字符串的方式来跳转,这种方式很简单但是不能传递参数:this.$router.push("home");对象想要传递参数主要就是以对象的方式来写,分为两种方…

  • JUC多线程:创建线程的四种方式

    JUC多线程:创建线程的四种方式

  • Inputstream_java input

    Inputstream_java inputimportjava.io.File;importjava.io.FileInputStream;importjava.io.IOException;importjava.io.InputStream;publicclassInputStreamDemo{/**InputStream字节输入流*FileInputStream:文件字节输入…

发表回复

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

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