Heat Wave（热浪）附超大数据

本文主要是介绍Heat Wave（热浪）附超大数据，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Heat Wave（热浪）

来源：USACO2009 October

题目描述

The good folks in Texas are having a heatwave this summer. Their Texas Longhorn cows make for good eating but are not so adept at creating creamy delicious dairy products. Farmer John is leading the charge to deliver plenty of ice cold nutritious milk to Texas so the Texans will not suffer the heat too much.

FJ has studied the routes that can be used to move milk from Wisconsin to Texas. These routes have a total of T (1 <= T <= 2,500) towns conveniently numbered 1..T along the way (including the starting and ending towns). Each town (except the source and destination towns) is connected to at least two other towns by bidirectional roads that have some cost of traversal (owing to gasoline consumption, tolls, etc.). Consider this map of seven towns; town 5 is the

source of the milk and town 4 is its destination (bracketed integers represent costs to traverse the route):
这里写图片描述（From：Luogu.org）
Traversing 5-6-3-4 requires spending 3 (5->6) + 4 (6->3) + 3 (3->4) = 10 total expenses.

Given a map of all the C (1 <= C <= 6,200) connections (described as two endpoints R1i and R2i (1 <= R1i <= T; 1 <= R2i <= T) and costs (1 <= Ci <= 1,000), find the smallest total expense to traverse from the starting town Ts (1 <= Ts <= T) to the destination town Te (1 <= Te <= T).

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。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)最小的总费用。
输入输出格式
输入格式：

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

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

输出格式：

一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。
输入输出样例
输入样例#1：

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

输出样例#1：

7
输入样例#2：

超大数据，上面的账号是我的Luogu账号，欢迎关注

输出样例#2：

1159

绪言

今天借USACO上的这个题学习一下SPFA，捎带着复习一下链表（如果有不理解链表的请移步来自Stockholm的链表入门，那里有非常详尽的解释）
然后就是这个超大的数据，本人欲从洛谷上下载而不得（文件太大，不允许下载），所以就找了一个以前的。

思路

这个题要用到SPFA，所谓SPFA的来历啥的就不再絮叨了，想知道的移步百度百科，关于SPFA入门在接下来会有一篇文章专门聊这件事情（望顶）。
这个题算是一个SPFA或者dijikstra算法的模板题，是一个裸的单源最短路问题，存起来最好要用链表。

数据处理

值得注意的是，在开结构体数组的时候，要开到6201*2的位置，因为这个题的每一条路都是双向路。处理如下：

        for(i=1;i<=m;i++){x=r(),y=r(),w=r();//这里的r（）是读入优化a[gs[x]].nxt=&a[i*2-1];//下一个的指针a[gs[y]].nxt=&a[i*2];gs[x]=i*2-1;//gs[x]用来记录最后一条从x出发的路//不过现在看来好像没啥用。。。gs[y]=i*2;if(!s[x]) s[x]=i*2-1;//s[x]是用来记录第一条从x出发的路，这个//还是有用的。if(!s[y]) s[y]=i*2;a[i*2-1].d=y,a[i*2-1].v=w;a[i*2].d=x,a[i*2].v=w;}

其他初始化步骤

这道题我是用了SPFA。
我们还需要一个queue来存节点，所以先把start点push进去。需要一个数组存从start点到某点的最短路程len[]。
初始化使len[start]=0，数组内其余元素=∞。

SPFA

其余的就是SPFA的相关技巧了，在此不再赘述。
在这里上我的SPFA代码

void spfa(int xx)
{struct data *p=&a[s[xx]];while(!q.empty()){p=&a[s[q.front()]];xx=q.front();q.pop();while(p!=NULL){if(len[p->d]>p->v+len[xx]){q.push(p->d);len[p->d]=p->v+len[xx];}p=p->nxt;}}
}

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
queue<int> q;
int f[4000];
struct edge
{int to,dis;edge* next=NULL;
}head[4001];
void add(int from,int to,int dis)
{edge* p;p=new edge;p->to=to,p->dis=dis;p->next=head[from].next;head[from].next=p;
} 
int read()
{int f=1,p=0;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return f*p;
}
int n,m,a,b;
int spfa(int i)
{edge* p;memset(f,0x7f,sizeof(f));q.push(i);f[i]=0;while(!q.empty()){i=q.front();p=&head[i];q.pop();for(;p!=NULL;p=p->next){if(f[p->to]>f[i]+p->dis){q.push(p->to);f[p->to]=f[i]+p->dis;}}}
}
int main()
{freopen("in.txt","r",stdin);n=read(),m=read();a=read(),b=read();for(int u,v,e,i=1;i<=m;i++){u=read(),v=read(),e=read();add(u,v,e),add(v,u,e);}spfa(a);printf("%d",f[b]);return 0;
}