首页 > 代码库 > AC日记——热浪 codevs 1557 （最短路模板题）
AC日记——热浪 codevs 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)
思路：
裸spfa;
来，上代码:
#include<queue>#include<cstdio>#include<iostream>using namespace std;struct node { int to,dis,next;};struct node edge[12801];int num_head,num_edge,num,start,end,head[2501],dis[2501];char word;void spfa(int all_from){ queue<int>que; bool if_in_spfa[2501]; for(int i=1 ; i<=num_head ; i++) dis[i]=99990000,if_in_spfa[i]=false; dis[all_from]=0; if_in_spfa[all_from]=true; que.push(all_from); int cur_1; while(!que.empty()) { cur_1=que.front(); que.pop(); for(int i=head[cur_1] ; i ; i=edge[i].next) { if(dis[cur_1]+edge[i].dis<dis[edge[i].to]) { dis[edge[i].to]=dis[cur_1]+edge[i].dis; if(!if_in_spfa[edge[i].to]) { if_in_spfa[edge[i].to]=true; que.push(edge[i].to); } } } if_in_spfa[cur_1]=false; }}inline void read_int(int &now_001){ now_001=0;word=getchar(); while(word<‘0‘||word>‘9‘) word=getchar(); while(word<=‘9‘&&word>=‘0‘) { now_001=now_001*10+(int)(word-‘0‘); word=getchar(); }}inline void edge_add(int from,int to,int dis){ num++; edge[num].to=to; edge[num].dis=dis; edge[num].next=head[from]; head[from]=num;}int main(){ ios::sync_with_stdio(false); read_int(num_head),read_int(num_edge),read_int(start),read_int(end); int from,to,dis1; for(int i=1 ; i<=num_edge ; i++) { read_int(from),read_int(to),read_int(dis1); edge_add(from,to,dis1); edge_add(to,from,dis1); } spfa(start); printf("%d\n",dis[end]); return 0;}
AC日记——热浪 codevs 1557 （最短路模板题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。