1557 热浪

1557 热浪

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

题目描述 Description

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇,方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用(包括油费,过路费等等)。

给定一个地图,包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs,终点Re (1 <= Rs <= T; 1 <= Re <= T),和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

输入描述 Input Description

第一行: 4个由空格隔开的整数: T, C, Ts, Te

第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci

输出描述 Output Description

一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

样例输入 Sample Input

7 11 5 4

2 4 2

1 4 3

7 2 2

3 4 3

5 7 5

7 3 3

6 1 1

6 3 4

2 4 3

5 6 3

7 2 1

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

5->6->1->4 (3 + 1 + 3)

分类标签 Tags 点此展开

暂无标签

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int MAXN=30001;
 7 const int maxn=0x7fffffff;
 8 struct node
 9 {
10     int u;
11     int v;
12     int w;
13     int next;
14 }edge[MAXN]; 
15 int num=1;
16 int head[MAXN];
17 int n,m,begin,end;
18 int dis[MAXN];
19 int vis[MAXN];
20 void spfa()
21 {
22     for(int i=1;i<=n;i++)dis[i]=maxn;
23     queue<int>q;
24     vis[begin]=1;
25     q.push(begin);
26     dis[begin]=0;
27     while(q.size()!=0)
28     {
29         int p=q.front();
30         q.pop();
31         vis[p]=0;
32         for(int i=head[p];i!=-1;i=edge[i].next)
33         {
34             if(dis[edge[i].v]>dis[p]+edge[i].w&&dis[p]!=maxn)
35             {
36                 dis[edge[i].v]=dis[p]+edge[i].w;
37                 if(vis[edge[i].v]==0)
38                 {
39                     q.push(edge[i].v);
40                     vis[edge[i].v]=1;
41                 }
42             }
43         }
44     }
45     printf("%d",dis[end]);
46 }
47 int main()
48 {
49     scanf("%d%d%d%d",&n,&m,&begin,&end);
50     for(int i=1;i<=n;i++)head[i]=-1;
51     for(int i=1;i<=m;i++)
52     {
53         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
54         edge[num].next=head[edge[num].u];
55         head[edge[num].u]=num++;
56         edge[num].w=edge[num-1].w;
57         edge[num].u=edge[num-1].v;
58         edge[num].v=edge[num-1].u;
59         edge[num].next=head[edge[num].u];
60         head[edge[num].u]=num++;
61     }
62     spfa();
63     return 0;
64 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏域名资讯

米友售出“温州、王者”2字母域名wz.cc

这一年里米市风云动荡,不乏大米交易。而极品域名二字母更是在众多大米中脱颖而出,以其简短大气的先天优势在米市中熠熠生辉,成为投资人和终端所追逐的对象。...

2070
来自专栏腾讯云安全的专栏

云下人团圆,云上我守护

嫦娥奔月 吴刚伐桂 玉兔捣药 天狗食月 …… 千米高空上的皎洁白月, 寄托了华夏儿女五千年来最浪漫的情怀。 八月十五的夜晚,完美无缺的圆月, 更是成为千家万...

641
来自专栏龙行天下CSIEM

科学瞎想系列之十七 能源危机是个神马鬼

能源危机是困扰当今世界可持续发展的难题之一,其实从严格意义上来讲,"能源危机"是一个伪命题,根据能量守恒定律,宇宙中的能量即不会无中生有也不会无故泯灭。...

3376
来自专栏机器人网

看懂了这些机械动图,再复杂的机构原理也难不倒你了

1、涡轮增压 Turbo Charger ? 大家可能会觉得涡轮增压装置非常复杂,其实并不复杂,涡轮增压装置主要是由涡轮室和增压器组成。首先是涡轮室的进气口与发...

2985
来自专栏大数据钻研

因为太难而被禁用的17道Google面试题

即使是最成功的公司,它的招聘过程有时也会很不靠谱,经常会出一些奇怪的看似没有答案的面试问题,但标准答案却让应聘者还没来得及接近「起跑线」就被「退赛」了。Goog...

2969
来自专栏互扯程序

程序猿一定要知道的&过年&习俗

农历正月初一是春节,又叫阴历(农历)年,俗称“过年”。这是我国民间最隆重、最热闹的一个古老传统节日。春节是汉族最重要的节日。 今天是大年三十 辛辛苦苦忙了一年...

2843
来自专栏程序人生 阅读快乐

Linus Torvalds:只是为了好玩——Linux 之父林纳斯自传

Linux之父Linus Torvalds的自传,也是Linus唯一一本书。Linus以调侃的语气讲述了自己的成长经历,在他看来,一切都是为了好玩儿,兴趣引发革...

1342
来自专栏大数据文摘

脑洞 | 把圆周率π用钢琴弹出来,是种什么体验?

1661
来自专栏杨熹的专栏

写作需要学习

上周写了三篇,这是本周第二篇,这几篇都只是在用自己的老底,而没有去学习如何写作。如果一直都是在记流水账,那即使坚持100天也未必能达到想要的效果。 今日思考:如...

3188
来自专栏量子位

Python的“仁慈独裁者”累觉不爱,宣布退位

1314

扫码关注云+社区

领取腾讯云代金券