我记得我当时刚接触信奥的时候，旁边的学长页面上显示的是a了这道题，当时的想着，什么时候我能把这道题写出来我就厉害了，然而今天发现自己，，，不说了，看题。
前几天，我在卡了很长时间图论后，终于学了克鲁斯卡尔，算是打破了我原来图论的空白，而今天我看着dalao的代码学了一遍了spfa，（迪杰斯特拉往后放放吧，尝试多次无功而返的痛啊~~~），
先看一个板子：
首先呢这是luoguP3371 【模板】单源最短路径（弱化版）(不卡spfa
这是spfa的模板
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
struct edge {
ll from;//与这条表最近的父亲节点一样的边的编号
ll to;//此边的子节点
ll w;//此边的权值
};
inline ll read(){//读入优化
int x = 0;int f = 1;char c = getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-f;
c=getchar();
}
while(c<='9'&&c>='0'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
const ll maxn = 500521;
const ll INF = 2147483647;
struct edge e[maxn];
int n;
int m;
int s;
int p;
int head[maxn];
int dis[maxn];//s点到某点的距离
int vis[maxn];//该点是否进队0未进，1已进
queue<int>que;
void add(int a,int b,int c){//邻接表
p++;
e[p].to = b;
e[p].w = c;
e[p].from = head[a];
head[a] = p;//以某点为父亲节点引出的最后一条边
}
void spfa(){
for(int i=1;i<=n;i++){
dis[i] = INF ;//初始化
vis[i] = 0;//记录一个点是否在队列中
}
que.push(s);//第一个顶点入队
dis[s] = 0;//初始化
vis[s] = 1; //s点已经入队
while(!que.empty()){//队列如果不是空的
//队列空时返回true
int u = que.front();//取出队首
que.pop();//弹出该点
vis[u] = 0;//该点出队
for(int i=head[u];i;i=e[i].from){//遍历邻接表
int v = e[i].to;
if(dis[v]>dis[u]+e[i].w){
//如果s到u点再到v点的距离小于当前已知的最短距离
dis[v] = dis[u]+e[i].w;//更新数据
if(vis[v]==0)//未入队
{
vis[v] = 1;//入队
que.push(v);
}
}
}
}
return；//想着写上算是一个好习惯吧
}
int main(){
n = read();m = read();s = read();
for(int i=1;i<=m;i++){
int u,v,j;
u = read();
v = read();
j = read();
add(u,v,j);
}
spfa();
for(int i=1;i<=n;i++){
if(s==i)printf("0 ");
else printf("%d ",dis[i]);
}
//system("pause");
return 0;
}
spfa要点步骤：
1.邻接表存边；
2.初始化，dis数组与vis数组；
3.从起点开始找，所以起点先入队；
4循环遍历邻接表，将符合条件的各点依次推入队列；
5.在循环遍历的同时更新每个点的数据，并入队；
好了看了spfa的板子再来看这道题就简单多了；
题目描述
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):
[1]----1---[3]-
/ \
[3]---6---[4]---3--[3]--4
/ / /|
5 --[3]-- --[2]- |
\ / / |
[5]---7---[2]--2---[3]---
| /
[1]------
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
说明
【样例说明】
5->6->1->4 (3 + 1 + 3)
首先呢，这是一个无向图，由此可以知道，我们存边的时候需要存两次，正着存一次，反着存一次；其次呢，好吧，其次就是输出是输出dis[te],在我的代码里是dis[h];
我呢就是模板复制粘贴修改一下，就过了,附AC代码；
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
struct edge {
ll from;//与这条表最近的父亲节点一样的边的编号
ll to;//此边的子节点
ll w;//此变得权值
};
inline ll read(){
int x = 0;int f = 1;char c = getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-f;
c=getchar();
}
while(c<='9'&&c>='0'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
const ll maxn = 500521;
const ll INF = 2147483647;
struct edge e[maxn];
int n;
int h;
int m;
int s;
int p;
int head[maxn];
int dis[maxn];
int vis[maxn];
queue<int>que;
void add(int a,int b,int c){
p++;
e[p].to = b;
e[p].w = c;
e[p].from = head[a];
head[a] = p;//以某点为父亲节点引出的最后一条边
}
void spfa(){
for(int i=1;i<=n;i++){
dis[i] = INF ;//初始化
vis[i] = 0;//记录一个点是否在队列中
}
que.push(s);//第一个顶点入队
dis[s] = 0;//初始化
vis[s] = 1;
//s点已经入队
while(!que.empty()){//队列如果不是空的
//队列空时返回true
int u = que.front();//取出队首
que.pop();//弹出该点
vis[u] = 0;//该点出队
for(int i=head[u];i;i=e[i].from){
int v = e[i].to;
if(dis[v]>dis[u]+e[i].w){
//如果s到u点再到v点的距离小于当前已知的最短距离
dis[v] = dis[u]+e[i].w;//更新数据
if(vis[v]==0)//未入队
{
vis[v] = 1;//入队
que.push(v);
}
}
}
}
}
int main(){
n = read();m = read();s = read();h=read();
for(int i=1;i<=m;i++){
int u,v,j;
u = read();
v = read();
j = read();
add(u,v,j);
add(v,u,j);
}
spfa();
printf("%d ",dis[h]);
//system("pause");
return 0;
}
网友评论