title: 最短路
date: 2018-07-27 22:36:50
tags:
- acm
- 算法
- 图论
概论
最短路主要是寻找某个有图问题从起始点到终点的最短的路，，，这是最基本的一种情况，，，由此可以变形出各种各样的其他题型，，，，
本篇主要有 图的储存 , Dijstra算法 ， SPFA算法 , Floyd算法 , 以及几道练习题和题解。。。
图的储存
一般来说图的储存有好几种，，，例如 邻接矩阵 , 邻接表 , 前向星 , 链式前向星,,,
临界矩阵
邻接矩阵是直接利用一个二维数组对边的关系进行存储，矩阵的第i行第j列的值 表示 i -> j 这条边的权值；特殊的，如果不存在这条边，用一个特殊标记来表示；如果i == j，则权值为0。它的优点是实现非常简单，而且很容易理解；缺点也很明显，如果这个图是一个非常稀疏的图，图中边很少，但是点很多，就会造成非常大的内存浪费，点数过大的时候根本就无法存储
一般来说，做题中都是用一个二维向量vector
邻接表
邻接表是图中常用的存储结构之一，每个顶点都有一个链表，这个链表的数据表示和当前顶点直接相邻的顶点（如果边有权值，还需要保存边权信息）。邻接表的优点是对于稀疏图不会有数据浪费，缺点就是实现相对麻烦，需要自己实现链表，动态分配内存。
前向星
前向星是以存储边的方式来存储图，先将边读入并存储在连续的数组中，然后按照边的起点进行排序，这样数组中起点相等的边就能够在数组中进行连续访问了。它的优点是实现简单，容易理解，缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序，带来了时间开销，实用性也较差，只适合离线算法。
链式前向星
链式前向星和邻接表类似，也是链式结构和线性结构的结合，每个结点i都有一个链表，链表的所有数据是从i出发的所有边的集合（对比邻接表存的是顶点集合），边的表示为一个四元组(u, v, w, next)，其中(u, v)代表该条边的有向顶点对，w代表边上的权值，next指向下一条边。
具体的，我们需要一个边的结构体数组 edge[MAXM]，MAXM表示边的总数，所有边都存储在这个结构体数组中，并且用head[i]来指向 i 结点的第一条边。
边的结构体声明如下：
struct EDGE {
int u, v, w, next;
EDGE() {}
EDGE(int _u, int _v, int _w, int _next) {
u = _u, v = _v, w = _w, next = _next;
}
}edge[MAXM];
初始化所有的head[i] = INF，当前边总数 edgeCount = 0
每读入一条边，调用addEdge(u, v, w)，具体函数的实现如下：
void addEdge(int u, int v, int w)
{
edge[ edgeCount ] = EDGE(u, v, w, head[u]);
head[u] = edgeCount ++;
}
这个函数的含义是每加入一条边(u, v)，就在原有的链表结构的首部插入这条边，使得每次插入的时间复杂度为O(1)，所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现，空间上没有浪费，时间上也是最小开销。
调用的时候只要通过head[i]就能访问到由 i 出发的第一条边的编号，通过编号到edge数组进行索引可以得到边的具体信息，然后根据这条边的next域可以得到第二条边的编号，以此类推，直到next域为INF（这里的INF即head数组初始化的那个值，一般取-1即可）。
集训时的模板，，，
const int maxn = 1e5; //无向图的话实际要开边数两倍的空间
int head[maxn]; //head[i]表示以i为起点的最后一条边的编号
struct edge
{
int to; //这条变得终点
int w; //这条变得权值
int last; //与自己起点相同的上一条边的编号
}Edge[maxm];
int cnt; //记录Edge数据里面的边用到了哪里
void add(int u , int v , int w) //加一条边，起点， 终点，权值
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u]; //将编号为cnt的边加入
head[u] = cnt++; //加边后，cnt为以u为起点的最后一条边
}
图的遍历
向量储存方式
int len = g[i].size();
for (int j = 0; j < len; j++)
int v = g[i][j]; //得到与i相连的所有节点
前向星储存方式
for (int j = head[i]; j != -1; j = Edge[j].last)
{
int v = Edge[j].to;
}
接下来重头戏，，，，
最短路
Dijkstra算法
Dijkstra算法适用于求 边权为正 ， 从单个原点出发的最短路。实际他能求初始点到其他所有顶点的最短路径，例如dis[i]表示原点到i这个节点的最短路的值，，，，实际上是基于bfs搜索的
对于一个有向图或无向图，所有边权为正（边用邻接矩阵的形式给出），给定a和b，求a到b的最短路，保证a一定能够到达b。这条最短路是否一定存在呢？答案是肯定的。相反，最长路就不一定了，由于边权为正，如果遇到有环的时候，可以一直在这个环上走，因为要找最长的，这样就使得路径越变越长，永无止境，所以对于正权图，在可达的情况下最短路一定存在，最长路则不一定存在。这里先讨论正权图的最短路问题。
最短路满足最优子结构性质，所以是一个动态规划问题。最短路的最优子结构可以描述为：
D(s, t) = {Vs ... Vi ... Vj ... Vt}表示s到t的最短路，其中i和j是这条路径上的两个中间结点，那么D(i, j)必定是i到j的最短路，这个性质是显然的，可以用反证法证明。
基于上面的最优子结构性质，如果存在这样一条最短路D(s, t) = {Vs ... Vi Vt}，其中i和t是最短路上相邻的点，那么D(s, i) = {Vs ... Vi} 必定是s到i的最短路。Dijkstra算法就是基于这样一个性质，通过最短路径长度递增，逐渐生成最短路。
Dijkstra算法是最经典的最短路算法，用于计算正权图的单源最短路（Single Source Shortest Path，源点给定，通过该算法可以求出起点到所有点的最短路），它是基于这样一个事实：如果源点到x点的最短路已经求出，并且保存在d[x] ( 可以将它理解为D(s, x) )上，那么可以利用x去更新 x能够直接到达的点 的最短路。即：
d[y] = min{ d[y], d[x] + w(x, y) } y为x能够直接到达的点，w(x, y) 则表示x->y这条有向边的边权
具体算法描述如下：对于图G = <V, E>，源点为s，d[i]表示s到i的最短路，visit[i]表示d[i]是否已经确定(布尔值)。
- 初始化 所有顶点 d[i] = INF, visit[i] = false，令d[s] = 0；
- 从所有visit[i]为false的顶点中找到一个d[i]值最小的，令x = i; 如果找不到，算法结束；
- 标记visit[x] = true, 更新和x直接相邻的所有顶点y的最短路： d[y] = min{ d[y], d[x] + w(x, y) }
第三步中如果y和x并不是直接相邻，则令w(x, y) = INF）
集训时的模板:
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 105;
const int maxm = 20020;
int head[maxn];
int dis[maxn];
int cnt;
int n , m;
//存图
void init()
{
memset(head , -1 , sizeof(head));
// memset(dis , inf , sizeof(dis));
// dis[1] = 0;
cnt = 0;
}
struct edge
{
int to;
int w;
int last;
}Edge[maxm];
void add(int u , int v , int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
//节点
struct node
{
int u;
int w;
bool operator < (const node &res)const //优先队列使用
{
return w > res.w;
}
node (int _u , int _w) //入队使用
{
u = _u;
w = _w;
}
};
//Dijkstra算法，，，
void Dijkstra() //求原点到终点的最短距离，结果在dis[i]中
{
for (int i = 1; i <= n; i++) //将每个节点值置为无穷大，，
dis[i] = inf;
dis[1] = 0; //原点到自身距离为0
priority_queue<node> q; //优先队列
while (!q.empty()) q.pop();
q.push(node(1 , 0));
while (!q.empty())
{
node nx = q.top();
q.pop();
int u = nx.u;
for (int i = head[u]; i != -1; i = Edge[i].last)
{
int to = Edge[i].to;
int w = Edge[i].w;
if (dis[u] + w < dis[to])
{
dis[to] = dis[u] + w;
q.push(node(to , dis[to]));
}
}
}
}
SPFA算法
Dijlstra算法只能处理正权值的图，，，可能出现负环，，会一直走下去，，而SPFA则可以处理有负权值的图，，
维护一个队列，里面存放所有需要进行迭代的点，初始时队列中只有一个原点s，用一个布尔数组记录每一个点是否在队列中，，，
大佬的表达:
SPFA( Shortest Path Faster Algorithm )是基于Bellman-Ford的思想，采用先进先出(FIFO)队列进行优化的一个计算单源最短路的快速算法。
类似Bellman-Ford的做法，我们用数组d记录每个结点的最短路径估计值，并用链式前向星来存储图G。利用一个先进先出的队列用来保存待松弛的结点，每次取出队首结点u，并且枚举从u出发的所有边(u, v)，如果d[u] + w(u, v) < d[v]，则更新d[v] = d[u] + w(u, v)，然后判断v点在不在队列中，如果不在就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
只要最短路径存在，SPFA算法必定能求出最小值。因为每次将点放入队尾，都是经过松弛操作达到的。即每次入队的点v对应的最短路径估计值d[v]都在变小。所以算法的执行会使d越来越小。由于我们假定最短路一定存在，即图中没有负权圈，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。
那么最短路径不存在呢？如果存在负权圈，并且起点可以通过一些顶点到达负权圈，那么利用SPFA算法会进入一个死循环，因为d值会越来越小，并且没有下限，使得最短路不存在。那么我们假设不存在负权圈，则任何最短路上的点必定小于等于n个（没有圈），换言之，用一个数组c[i]来记录i这个点入队的次数，所有的c[i]必定都小于等于n，所以一旦有一个c[i] > n，则表明这个图中存在负权圈。
接下来给出SPFA更加直观的理解，假设图中所有边的边权都为1，那么SPFA其实就是一个BFS（Breadth First Search，广度优先搜索），对于BFS的介绍可以参阅搜索入门。BFS首先到达的顶点所经历的路径一定是最短路(也就是经过的最少顶点数)，所以此时利用数组记录节点访问可以使每个顶点只进队一次，但在至少有一条边的边权不为1的带权图中，最先到达的顶点的路径不一定是最短路，这就是为什么要用d数组来记录当前最短路估计值的原因了。
集训时的模板:
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 30010;
int head[maxn];
int dis[maxn];
int in[maxn]; //in[i]表示点i的入队次数
bool vis[maxn]; //vis[i]表示点i是否在队列中
int cnt;
int n , m;
//int s , t;
void init()
{
memset(head , -1 , sizeof(head));
cnt = 0;
}
struct edge
{
int to;
int w;
int last;
}Edge[maxm];
void add(int u , int v , int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
struct node
{
int u;
int w;
bool operator < (const node &res)const
{
return w > res.w;
}
node (int _u , int _w)
{
u = _u;
w = _w;
}
};
int spfa(int s)
{
queue<int> q;
dis[s] = 0;
memset(vis , false , sizeof(vis));
memset(in , 0 , sizeof(ln));
memset(dis , inf , sizeof(dis));
dis[s] = 0;
q.push(s);
vis[s] = true;
in[s] = 1; //顶点入队vis标记，，，同时统计顶点的入队次数
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false; //对头元素出队，并且消除标记
for (int i = head[u]; i != -1; i = Edge[i].last) //遍历顶点u的邻接表
{
int v = Edge[i].to;
int w = Edge[i].w;
if (dis[u] + w < dis[v])
{
dis[v] = dis[u] + w; //松弛
if (!vis[v]) //顶点v不在队内
{
vis[v] = true; //标记
in[v]++; //统计次数
q.push(v); //入队
if (in[v] >= n) //超出入队次数上限，说明有负环
return 1;
}
}
}
}
return -1; //存在负环返回-1
}
Floyd算法
如果需要求任意两点之间的距离，不必调用n次dijstra或者Bellman-ford算法，可以使用Floyd-Warshall算法
- Floyd算法利用 动态规划 ，，
- 用d[i][j][k]表示从i到j，经过编号不超过k的点所得到的最短距离，则d[i][j][k] = min{d[i][j][k - 1] , d[i][k][k - 1] + d[k][j][k - 1]}
最后介绍一个 求任意两点最短路 的算法，很显然，我们可以求n次单源最短路（枚举起点），但是下面这种方法更加容易编码，而且很巧妙，它也是基于动态规划的思想。
令d[i][j][k]为只允许经过结点[0, k]的情况下，i 到 j的最短路。那么利用最优子结构性质，有两种情况：
a. 如果最短路经过k点，则d[i][j][k] = d[i][k][k-1] + d[k][j][k-1];
b. 如果最短路不经过k点，则d[i][j][k] = d[i][j][k-1];
于是有状态转移方程： d[i][j][k] = min{ d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1] } (0 <= i, j, k < n)
这是一个3D/0D问题，只需要按照k递增的顺序进行枚举，就能在O(n3)的时间内求解，又第三维的状态可以采用滚动数组进行优化，所以空间复杂度为O(n2)。
习题
Problem A: 实习生averyboy
Time Limit: 2 Sec Memory Limit: 128 MB
Description
averyboy现在在实习。每天早上他要步行去公司上班，你肯定知道，他是一个非常男孩，所以他会选择最短的路去公司。现在给你averyboy到公司途中的若干个站点，标号为1~N,averyboy的开始在1号站点，它的公司在N号站点，然后给你若干条边代表站点有路可以通过（可能会有重边）。现在你需要告诉averyboy他到公司的最短路径是多少。
Input
第一行一个整数T（T <= 5）代表测试数据的组数
接下来T组测试数据。
每组测试数据第一行为两个整数N，M(1 <= N <= 100, 0 <= M <= 10000)代表站点的个数和边的条数
接下来M行，每一行三个数u, v, w代表站点u,v之间有一条无向边，边的权值为w(1 <= u, v <= N, 0 <= w <= 1000)
Output
对于每组测试数据，如果存在路径使得averyboy能够到达公司，输出一个整数代表这个最短路径的长度，反之输出averyboynb
Sample Input
2
3 2
1 2 1
2 3 1
3 1
1 2 1
Sample Output
2
averyboynb
我的代码，，，
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 105;
const int maxm = 20020; //无向图边开两倍
int head[maxn];
int dis[maxn];
int cnt;
int n , m;
void init()
{
memset(head , -1 , sizeof(head));
// memset(dis , inf , sizeof(dis));
// dis[1] = 0;
cnt = 0;
}
struct edge
{
int to;
int w;
int last;
}Edge[maxm];
void add(int u , int v , int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
struct node
{
int u;
int w;
bool operator < (const node &res)const
{
return w > res.w;
}
node (int _u , int _w)
{
u = _u;
w = _w;
}
};
void Dijkstra()
{
for (int i = 1; i <= n; i++)
dis[i] = inf;
priority_queue<node> q;
while (!q.empty()) q.pop();
dis[1] = 0;
q.push(node(1 , 0));
while (!q.empty())
{
node nx = q.top();
q.pop();
int u = nx.u;
for (int i = head[u]; i != -1; i = Edge[i].last)
{
int to = Edge[i].to;
int w = Edge[i].w;
if (dis[u] + w < dis[to])
{
dis[to] = dis[u] + w;
q.push(node(to , dis[to]));
}
}
}
}
int main()
{
//ios_base::sync_with_stdio(0);
//freopen("data.in", "r", stdin);
// freopen("test.out", "w", stdout);
int t;
//cin >> t;
scanf("%d" , &t);
while (t--)
{
//cin >> n >> m;
scanf("%d%d" , &n , &m);
int u , v , w;
init();
for (int i = 0; i < m; i++)
{
//cin >> u >> v >> w;
scanf("%d%d%d" , &u , &v , &w);
add(u , v , w);
add(v , u , w);
}
Dijkstra();
// for (int i = 0; i < n; i++)
// cout << dis[i] << endl;
if (dis[n] != inf)
//cout << dis[n] << endl;
printf("%d
" , dis[n]);
else
//cout << "averyboynb" << endl;
printf("averyboynb
");
}
return 0;
}
学长的代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 10;
const int maxe = 10000 + 10;
const int inf = 0x3f3f3f3f;
int N, M;
int dis[maxn];
int cnt;
int head[maxn];
struct edge{
int to, w, last;
}Edge[maxe<<1];
void init()
{
cnt = 1;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
struct node{
int u, w;
node(int _u, int _w){
u = _u;
w = _w;
}
bool operator <(const node &res) const{
return w > res.w;
}
};
int Dijkstra()
{
for(int i = 1; i <= N; i++) dis[i] = inf;
priority_queue<node> q;
dis[1] = 0;
q.push(node(1, 0));
while(!q.empty())
{
node nx = q.top();
q.pop();
int u = nx.u;
for(int i = head[u]; i != -1; i = Edge[i].last)
{
int v = Edge[i].to;
int w = Edge[i].w;
if(dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
q.push(node(v, dis[v]));
}
}
}
return dis[N];
}
int main()
{
//freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &N, &M);
init();
int u, v, w;
for(int i = 1; i <= M; i++)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
int ans = Dijkstra();
if(ans >= inf) printf("averyboynb
");
else printf("%d
", ans);
}
return 0;
}
Problem B: 实习生averyboy2
Time Limit: 1 Sec Memory Limit: 128 MB
Description
averyboy现在在实习。每天早上他要步行去公司上班，你肯定知道，他是一个非常男孩，所以他会选择最短的路去公司。现在给你averyboy到公司途中的若干个站点，标号为1~N,现在averyboy的起点可以是多个点，averyboy的终点也就是公司也可以是多个点，给你站点之间的边和它们的权值。现在你需要告诉averyboy他到公司的最短路径是多少（只需从任意一个起点开始到达任意一个终点就行）。
Input
第一行一个整数T（T <= 5）代表测试数据的组数
接下来T组测试数据。
每组测试数据第一行为两个整数N，M，k1, k2(1 <= N <= 1000, 0 <= M <= 10000)代表站点的个数和边的条数以及起点的个数，终点的个数（1 <= k1, k2 <= N）
接下来一行k1个数x[i]，代表averyboy起点（1 <= x[i] <= N)
接下来一行k2个数y[i]，代表终点(1 <= y[i] <= N)
接下来M行，每一行三个数u, v, w代表站点u,v之间有一条无向边（可能会有重边），边的权值为w(1 <= u, v <= N, 0 <= w <= 1000)
Output
对于每组测试数据，如果存在路径使得averyboy能够到达公司，输出一个整数代表这个最短路径的长度，反之输出averyboynb
Sample Input
1
4 5 2 2
1 4
2 3
1 2 1
2 3 2
3 4 4
1 3 3
1 4 5
Sample Output
1
HINT
选择起点为1终点为2，此时有最短路径1.
因为最短路主要是求两点之间的最短路，，对于这种多个起点和多个终点的可以先找一个 超级起点 原点s和一个 汇点t,,,构建这两个点到相应的每一个起点、终点的边，，并且权值为零，，，这样化求多个起点和终点之间的最短路为原点s和汇点t之间最短路，，，，
我的代码(当时做时dijkstra算法的模板打错了，，所以换spfa做的，，，差不多都):
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 30010;
int head[maxn];
int dis[maxn];
int ln[maxn];
bool vis[maxn];
int cnt;
int n , m , k1 , k2;
//int s , t;
void init()
{
memset(head , -1 , sizeof(head));
cnt = 0;
}
struct edge
{
int to;
int w;
int last;
}Edge[maxm];
void add(int u , int v , int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
struct node
{
int u;
int w;
bool operator < (const node &res)const
{
return w > res.w;
}
node (int _u , int _w)
{
u = _u;
w = _w;
}
};
int spfa(int s)
{
queue<int> q;
dis[s] = 0;
memset(vis , false , sizeof(vis));
memset(ln , 0 , sizeof(ln));
memset(dis , inf , sizeof(dis));
dis[s] = 0;
q.push(s);
vis[s] = true;
ln[s] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = Edge[i].last)
{
int v = Edge[i].to;
int w = Edge[i].w;
if (dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
if (!vis[v])
{
vis[v] = true;
ln[v]++;
q.push(v);
if (ln[v] >= n)
return 1;
}
}
}
}
return -1;
}
int main()
{
//ios_base::sync_with_stdio(0);
int t;
//cin >> t;
scanf("%d" , &t);
while (t--)
{
//cin >> n >> m;
scanf("%d%d%d%d" , &n , &m , &k1 , &k2);
int u , v , w;
init();
//设原点s = 0;汇点t = n + 1;
for (int i = 0; i < k1; i++)
{
int tmp;scanf("%d" , &tmp);
add(0 , tmp , 0);
add(tmp , 0 , 0);
}
for (int i = 0; i < k2; i++)
{
int tmp;scanf("%d" , &tmp);
add(tmp , n + 1 , 0);
add(n + 1 , tmp , 0);
}
for (int i = 0; i < m; i++)
{
//cin >> u >> v >> w;
scanf("%d%d%d" , &u , &v , &w);
add(u , v , w);
add(v , u , w);
}
spfa(0);
if (dis[n + 1] != inf)
//cout << dis[n] << endl;
printf("%d
" , dis[n + 1]);
else
//cout << "averyboynb" << endl;
printf("averyboynb
");
}
return 0;
}
学长的代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 10;
const int maxe = 100000 + 10;
const int inf = 0x3f3f3f3f;
int N, M;
int k1, k2;
int dis[maxn];
int cnt;
int head[maxn];
vector<int> s1, s2;
struct edge{
int to, w, last;
}Edge[maxe<<2];
void init()
{
cnt = 1;
memset(head, -1, sizeof(head));
s1.clear();
s2.clear();
}
void add(int u, int v, int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
struct node{
int u, w;
node(int _u, int _w){
u = _u;
w = _w;
}
bool operator <(const node &res) const{
return w > res.w;
}
};
int Dijkstra()
{
for(int i = 0; i <= N + 1; i++) dis[i] = inf;
priority_queue<node> q;
dis[0] = 0;
q.push(node(0, 0));
while(!q.empty())
{
node nx = q.top();
q.pop();
int u = nx.u;
for(int i = head[u]; i != -1; i = Edge[i].last)
{
int v = Edge[i].to;
int w = Edge[i].w;
if(dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
q.push(node(v, dis[v]));
}
}
}
return dis[N + 1];
}
int main()
{
//freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d%d", &N, &M, &k1, &k2);
init();
int u, v, w;
for(int i = 1; i <= k1; i++)
{
scanf("%d", &u);
s1.push_back(u);
}
for(int i = 1; i <= k2; i++)
{
scanf("%d", &u);
s2.push_back(u);
}
for(int i = 1; i <= M; i++)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
for(int i = 0; i < k1; i++)
{
add(0, s1[i], 0);
add(s1[i], 0, 0);
}
for(int i = 0; i < k2; i++)
{
add(s2[i], N + 1, 0);
add(N + 1, s2[i], 0);
}
int ans = Dijkstra();
if(ans >= inf) printf("averyboynb
");
else printf("%d
", ans);
}
return 0;
}
Problem C: 商人averyboy
Time Limit: 2 Sec Memory Limit: 128 MB
Description
averyboy最近想买一个新的mac，所以他想赚点钱。所以他选择去卖书。现在有N个城市，书在每一个城市价格不一样，但是在同一个城市，买一本书和卖一本书的价格一样，然后如果城市x,y之间有一条权值为w的边，averyboy从城市x到y需要支付w费用，现在给你书在N个城市的价格和城市之间的边以及权值（N - 1条边，刚好使N个城市想连通），averyboy需要选择一个城市为起点，买一本书，然后跑到另外一个城市将这本书卖掉。averyboy数学不太好，你能告诉他他最多能赚多少钱吗？
Input
第一行一个整数T（T <= 5）代表测试数据的组数
接下来T组测试数据
每组测试数据第一行为一个正整数N（N <= 1e5）代表城市的个数
接下来一行N个整数a[i]，代表书在每个城市的价格(1 <= a[i] <= 10000)
接下来N - 1行，每行三个数u, v, w（1 <= u, v <= N, 1 <= w <= 1000）代表城市u,v之间有一条权值为w的边
Output
对于每组测试数据,输出一个整数，表示averyboy能赚到的最多的钱。
Sample Input
1
4
10 40 15 30
1 2 30
1 3 2
3 4 10
Sample Output
8
HINT
他选择从1号城市买书，到4号城市卖书，然后他买书和路费一共花费10 + 2 + 10 = 22，到了4号城市把书卖掉，赚30元，所以最终赚了30 - 22 = 8元，这种情况下他能赚的最多。
因为有加有减，点还有值，，，所以可以建立原点和汇点分离他的值，，也就是题里的买书钱和卖书钱，，，其中s到每一个点的权值为正的书价钱，，，t到每一个点的权值为负的书价钱，，，
又因为有负权值的边，，，所以选用SPFA算法，，，，对s做SPFA之后dis[t] = 买书钱 + 路费 - 卖书钱，，，这个dis[t]是最小的 ，，，，取负值即为卖书钱 - 买书钱 - 路费，，，也就是最终赚的最大值
我的代码：
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 500010;
const int maxm = 500020;
int head[maxn];
int dis[maxn];
int in[maxn];
bool vis[maxn];
int money[maxn];
int cnt;
int n;
//int s , t;
void init()
{
memset(head , -1 , sizeof(head));
cnt = 0;
}
struct edge
{
int to;
int w;
int last;
}Edge[maxm];
void add(int u , int v , int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
struct node
{
int u;
int w;
bool operator < (const node &res)const
{
return w > res.w;
}
node (int _u , int _w)
{
u = _u;
w = _w;
}
};
int spfa(int s)
{
queue<int> q;
dis[s] = 0;
memset(vis , false , sizeof(vis));
memset(in , 0 , sizeof(in));
memset(dis , inf , sizeof(dis));
dis[s] = 0;
q.push(s);
vis[s] = true;
in[s] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = Edge[i].last)
{
int v = Edge[i].to;
int w = Edge[i].w;
if (dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
if (!vis[v])
{
vis[v] = true;
in[v]++;
q.push(v);
if (in[v] >= n)
return 1;
}
}
}
}
return -1;
}
int main()
{
//ios_base::sync_with_stdio(0);
int t;
//cin >> t;
//freopen("data.in" , "r" , stdin);
scanf("%d" , &t);
while (t--)
{
//cin >> n >> m;
scanf("%d" , &n);
int u , v , w;
init();
int money[maxn];
for (int i = 1; i <= n; i++)
{
scanf("%d" , &money[i]);
}
for (int i = 1; i <= n; i++)
{
add(0 , i , money[i]); //0为原点
//add(i , 0 , money);
//add(n + 1 , i , -money);
add(i , n + 1 , -money[i]); //n + 1即为汇点，权值取负
}
for (int i = 1; i < n; i++)
{
scanf("%d%d%d" , &u , &v , &w);
add(u , v , w);
add(v , u , w);
}
spfa(0);
printf("%d
" , -dis[n + 1]);
}
return 0;
}
学长的代码:
不是用前向星存的图，，而且貌似思路与上面那个不同，，，先放在这，，之后再看一下
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 100;
int n;
int d[maxn];
bool visit[maxn];
int inf = 0x3f3f3f3f;
struct node{
int v;
int w;
node(int _v = 0, int _w = 0){
v = _v;
w = _w;
}
};
queue<node> q;
vector<pair<int ,int> > g[maxn];
int spfa()
{
memset(d, -inf, sizeof(d));
memset(visit, false, sizeof(visit));
while(!q.empty()) q.pop();
d[0] = 0;
q.push(node(0, 0));
while(!q.empty())
{
node nx = q.front();
q.pop();
int v = nx.v;
visit[v] = false;
for(int i = 0; i < g[v].size(); i++)
{
int u = g[v][i].first;
int ww = g[v][i].second;
if(d[v] + ww > d[u] && u != 0)
{
d[u] = d[v] + ww;
if(visit[u]) continue;
visit[u] = true;
q.push(node(u, d[u]));
}
}
}
if(d[n + 1] > 0) return d[n + 1];
else return 0;
}
void init()
{
for(int i = 0; i <= n + 1; i++)
{
g[i].clear();
}
}
int main()
{
//freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
init();
int u, v, w;
for(int i = 1; i <= n; i++)
{
scanf("%d", &w);
g[0].push_back(make_pair(i, w));
g[i].push_back(make_pair(0, w));
g[n + 1].push_back(make_pair(i, -w));
g[i].push_back(make_pair(n + 1, -w));
}
for(int i = 1; i < n; i++)
{
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(make_pair(v, -w));
g[v].push_back(make_pair(u, -w));
}
printf("%d
", spfa());
}
return 0;
}
Problem D: 老司机averyboy
Time Limit: 2 Sec Memory Limit: 128 MB
Description
averyboy不仅是一个非常男孩，他还是一位老司机。现在averyboy在开火车，一共有N个火车站，每个火车站出站口只有若干个出口，这些出口分别对应一些其他的火车站，代表如果从这一个出口开出火车，下一站将会达到该出口对应的火车站。每一个火车站有一个默认的出口，如果此次averyboy想要出站的出口不是默认出口，他将会被他的上级批评一次。现在averyboy需要从A站到B站，给你每一个火车站出站口的出口的情况，你需要告诉averyboy他最少要被批评多少次
Input
第一行一个整数T（T <= 5）代表测试数据的组数
接下来T组测试数据
每组测试数据的第一行三个整数N, A, B（1 <= N <= 100, 1 <= A, B <= N）分别代表火车站的数量以及averyboy的起点站和终点站
接下来N行数据，第i行第一个数为k，代表第i个火车站有k个出口，后面k个整数（k个整数可能会有若干个相同），代表每个出口通向的下一个火车站编号，k个数中的第一个表示这个火车站默认的出口。（0 <= k <= N）
Output
对于每组测试数据，如果A能够达到B，输出一个整数，代表averyboy最小被批评的次数反之输出averyboynb
Sample Input
2
3 2 1
2 2 3
2 3 1
2 1 2
3 1 2
2 3 2
1 3
1 1
Sample Output
0
1
根据题意默认的出口的权值可以设为0，其他的为1，，即加一次被批评的次数，，，最少的批评次数即为求最短路，，，
我的代码:
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 30010;
int head[maxn];
int dis[maxn];
int ln[maxn];
bool vis[maxn];
int cnt;
int n , acfun , bilibili;
//int s , t;
void init()
{
memset(head , -1 , sizeof(head));
cnt = 0;
}
struct edge
{
int to;
int w;
int last;
}Edge[maxm];
void add(int u , int v , int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
struct node
{
int u;
int w;
bool operator < (const node &res)const
{
return w > res.w;
}
node (int _u , int _w)
{
u = _u;
w = _w;
}
};
int spfa(int s)
{
queue<int> q;
dis[s] = 0;
memset(vis , false , sizeof(vis));
memset(ln , 0 , sizeof(ln));
memset(dis , inf , sizeof(dis));
dis[s] = 0;
q.push(s);
vis[s] = true;
ln[s] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = Edge[i].last)
{
int v = Edge[i].to;
int w = Edge[i].w;
if (dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
if (!vis[v])
{
vis[v] = true;
ln[v]++;
q.push(v);
if (ln[v] >= n)
return 1;
}
}
}
}
return -1;
}
int main()
{
//ios_base::sync_with_stdio(0);
int t;
//cin >> t;
scanf("%d" , &t);
while (t--)
{
//cin >> n >> m;
scanf("%d%d%d" , &n , &acfun , &bilibili);
int u , v , w;
init();
//设原点s = 0;汇点t = n + 1;
for (int i = 1; i <= n; i++)
{
int k;scanf("%d" , &k);
int t;scanf("%d" , &t);
add(i , t , 0); //默认出口
for (int j = 2; j <= k; j++)
{
scanf("%d" , &t); //会被批评的出口
add(i , t , 1);
}
}
spfa(acfun);
if (dis[bilibili] != inf)
//cout << dis[n] << endl;
printf("%d
" , dis[bilibili]);
else
//cout << "averyboynb" << endl;
printf("averyboynb
");
}
return 0;
}
学长的代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 10;
const int maxe = 10000 + 10;
const int inf = 0x3f3f3f3f;
int N, A, B;
int dis[maxn];
int cnt;
int head[maxn];
struct edge{
int to, w, last;
}Edge[maxe<<1];
void init()
{
cnt = 1;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int w)
{
Edge[cnt].to = v;
Edge[cnt].w = w;
Edge[cnt].last = head[u];
head[u] = cnt++;
}
struct node{
int u, w;
node(int _u, int _w){
u = _u;
w = _w;
}
bool operator <(const node &res) const{
return w > res.w;
}
};
int Dijkstra(int s, int t)
{
for(int i = 1; i <= N; i++) dis[i] = inf;
priority_queue<node> q;
dis[s] = 0;
q.push(node(s, 0));
while(!q.empty())
{
node nx = q.top();
q.pop();
int u = nx.u;
for(int i = head[u]; i != -1; i = Edge[i].last)
{
int v = Edge[i].to;
int w = Edge[i].w;
if(dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
q.push(node(v, dis[v]));
}
}
}
return dis[t];
}
int main()
{
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &N, &A, &B);
init();
for(int i = 1; i <= N; i++)
{
int k, x;
scanf("%d", &k);
for(int j = 1; j <= k; j++)
{
scanf("%d", &x);
if(j == 1) add(i, x, 0);
else add(i, x, 1);
}
}
int ans = Dijkstra(A, B);
if(ans >= inf) printf("averyboynb
");
else printf("%d
", ans);
}
return 0;
}
其他
没了，，，假期再看一遍看能再补些啥，，，，