题目描述
长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,⋯,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 ii 到游艇出租站 j 之间的租金为 r(i,j)（1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。
输入格式
第一行中有一个正整数 n，表示有 n 个游艇出租站。接下来的 n-1 行是一个半矩阵 r(i,j)（1≤i<j≤n）。
输出格式
输出计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金。
输入输出样例
输入 #1复制
3 5 15 7输出 #1复制
12说明/提示
n≤200，保证计算过程中任何时刻数值都不超过 10^6。
题解：本题测试数据并不大，所以可以使用简单的Floyd来解决。用一个二维数组来存图，a[i][j]=w即表示i中转站到j中转站需要费用w元。先将图初始化，自己到自己的费用为0元，其统统设为一个不可能的费用，然后用Floyd的三个for循环求出每两个中转站之间通过其他中转站能到达的最小费用。
#include <stdio.h>
int a[201][201];//存图
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) //初始化图
for(int j=1;j<=n;j++)
if(i==j) a[i][j]=0;//自己到自己费用设为0
else a[i][j]=99999;//假设各个站都没有连接,将费用设为一个不可能达到的最大值
for(int i=1;i<n;i++){//创建i到i+1~n的各个站的连接
for(int j=i+1;j<=n;j++){
int r;
scanf("%d",&r);
a[i][j]=r;
}
}
//Floyd经典语句
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
printf("%d",a[1][n]);
return 0;
} 题目描述
有一个 n 个点 m 条边的无向图，请求出从 s 到 t 的最短路长度。
输入格式
第一行四个正整数 n,m,s,t。 接下来 m 行，每行三个正整数 u,v,w，表示一条连接 u,v长为 w 的边。
输出格式
输出一行一个整数，表示答案。
输入输出样例
输入 #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说明/提示
【数据范围】
对于 100% 的数据，1≤n≤2500，1≤m≤6200，1≤w≤1000。【样例说明】
5→6→1→4 为最短路，长度为 3+1+3 = 7。
题解：本题最多有2500个点，用普通的Floyd或dfs会超时，所以本题用的更快的dijkstra，以s点为源点，求出到所有其他点的最短距离，到时候输出只输出到t点的最短距离即可。
#include <stdio.h>
#define inf 999999
int a[2501][2501],dis[2501];//a存图,dis存s点到各个点的最短路径
bool book[2501];//标记是否最短路径已确定
int main(){
int n,m,s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) a[i][j]=0;
else a[i][j]=inf;
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
a[u][v]=w;//无向图
a[v][u]=w;
}
book[s]=true;//将源点确定
for(int i=1;i<=n;i++)//初始化dis
dis[i]=a[s][i];
for(int i=1;i<=n-1;i++){//只需执行n-1次
int min=inf,u;
for(int j=1;j<=n;j++){//找未确定最短路径的最小值
if(!book[j]&&dis[j]<min){
min=dis[j];
u=j;
}
}
book[u]=true;//将该点最短路径确定
for(int j=1;j<=n;j++){
if(a[u][j]<inf&&dis[j]>dis[u]+a[u][j])//把通过其他点能更快的到达j的路径代替s点直接到j的路径
dis[j]=dis[u]+a[u][j];
}
}
printf("%d",dis[t]);//s到t的最短路径
} 题目描述
Farmer John is on a boat seeking fabled treasure on one of the N (1 <= N <= 100) islands conveniently labeled 1..N in the Cowribbean Sea.
The treasure map tells him that he must travel through a certain sequence A_1, A_2, ..., A_M of M (2 <= M <= 10,000) islands, starting on island 1 and ending on island N before the treasure will appear to him. He can visit these and other islands out of order and even more than once, but his trip must include the A_i sequence in the order specified by the map.
FJ wants to avoid pirates and knows the pirate-danger rating (0 <= danger <= 100,000) between each pair of islands. The total danger rating of his mission is the sum of the danger ratings of all the paths he traverses.
Help Farmer John find the least dangerous route to the treasure that satisfies the treasure map's requirement.
输入格式
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 describes the i_th island FJ must visit with a single integer: A_i
* Lines M+2..N+M+1: Line i+M+1 contains N space-separated integers that are the respective danger rating of the path between island i and islands 1, 2, ..., and N, respectively. The ith integer is always zero.
输出格式
* Line 1: The minimum danger that Farmer John can encounter while obtaining the treasure.
题意翻译
农夫约翰正驾驶一条小艇在牛勒比海上航行．
海上有 N(1≤N≤100) 个岛屿，用 1 到 N 编号．约翰从 1 号小岛出发，最后到达 N 号小岛．
一张藏宝图上说，如果他的路程上经过的小岛依次出现了 A1,A2,…,AM(2≤M≤10000) 这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数 Di,j(0≤Di,j≤100000) 来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？
输入输出格式
输入格式：
第一行：两个用空格隔开的正整数 N 和 M。
第二到第 M+1 行：第 i+1 行用一个整数 Ai 表示 FJ 必须经过的第 i 个岛屿
第 M+2 到第 N+M+1 行：第 i+M+1 行包含 N 个用空格隔开的非负整数分别表示 i 号小岛到第 1…N 号小岛的航线各自的危险指数。保证第 i 个数是 0。
输出格式 第一行：FJ 在找到宝藏的前提下经过的航线的危险指数之和的最小值。
说明 这组数据中有三个岛屿，藏宝图要求 FJ 按顺序经过四个岛屿：1 号岛屿、2 号岛屿、回到 1 号岛屿、最后到 3 号岛屿。每条航线的危险指数也给出了：航路(1,2),(2,3),(3,1) 和它们的反向路径的危险指数分别是 5,2,1。
FJ 可以通过依次经过 1,3,2,3,1,3 号岛屿以 77 的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求 (1,2,1,3)。我们避开了 1 号和 2 号岛屿之间的航线，因为它的危险指数太大了。
注意：测试数据中 a 到 b 的危险指数不一定等于 b 到 a 的危险指数！
Translated by @LJC00125
输入输出样例
输入 #1复制
3 4 1 2 1 3 0 5 1 5 0 2 1 2 0输出 #1复制
7
题解：本题的意思就是求按要求走完某些岛之后的最小危险指数，而且本题小岛数量的数据并不大，所以可以直接使用Floyd求出任意两个岛通过走其他岛到达后的最小危险指数，然后按照他给出的要求，计算出走完这些岛总的危险指数。
#include <stdio.h>
int e[110][110],map[10010];//e存图，map存必须经过的点
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d",&map[i]);
for(int i=1;i<=n;i++)//根据输出存图
for(int j=1;j<=n;j++){
int w;
scanf("%d",&w);
e[i][j]=w;//i->j的危险指数为w
}
for(int k=1;k<=n;k++)//Floyd计算出任意两个点之间的最小危险指数
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
int cnt=0;
for(int i=1;i<=m-1;i++)
cnt+=e[map[i]][map[i+1]];//按照地图要求走完并累加危险值
printf("%d\n",cnt);
return 0;
} 题目描述
A 国派出将军uim，对 B 国进行战略性措施，以解救涂炭的生灵。
B 国有 n 个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。
uim 发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为 key road。
uim 为了尽快使该国的物流系统瘫痪，希望炸毁铁路，以达到存在某两个城市无法互相通过铁路到达的效果。
然而，只有一发炮弹（A 国国会不给钱了）。所以，他能轰炸哪一条铁路呢？
输入格式
第一行 n，m (1≤n≤150，1≤m≤5000)，分别表示有 n 个城市，总共 m 条铁路。
以下 m 行,每行两个整数 a,b，表示城市 a 和城市 b 之间有铁路直接连接。
输出格式
输出有若干行。
每行包含两个数字 a，b，其中 a<b，表示 <a,b> 是 key road。
请注意：输出时，所有的数对 <a,b> 必须按照 a 从小到大排序输出；如果a 相同，则根据 b 从小到大排序。
输入输出样例
输入 #1复制
6 6 1 2 2 3 2 4 3 5 4 5 5 6输出 #1复制
1 2 5 6
题解：本题的知识点为“图的割线”，即删去一些线使图不再连通（即任意的两点不能相互到达），要实现这个操作需要用到tarjan。即用深搜从任意一点（因为始终要遍历整个图）开始遍历，记录每个点的实际时间戳和low时间戳（即能通过其他点访问到的更早的时间戳），如果从前往后遍历的两个点，不使用这条线能使后者的时间戳访问到更早的时间戳，那么这条线就不是割线，因为没有这条线也能使后面的点通过其他点返回去，整个图任意两点依旧连通；否则后者的low>前者的low,即没有这条线无法使后者能通过其他点与整个图连通,那么这条线就是"割线",也就是本题需要炸毁的地方。（割线更详细解说请自行搜索或者看啊哈算法）
#include <bits/stdc++.h>
using namespace std;
int e[160][160],num[160],low[160],idx,k,n,m,root;//e地图,num存时间戳,low存通过其他点能降低时间戳的值,idx时间戳
struct edge{//用结构体存边的两边顶点,以便排序
int pre;
int nxt;
}edges[5010];
bool com(struct edge a,struct edge b){//sort函数多级排序条件
if(a.pre<b.pre)
return true;
else{
if(a.pre==b.pre){
if(a.nxt<b.nxt)
return true;
else
return false;
}
else
return false;
}
}
void dfs(int cur,int fa){
idx++;
num[cur]=idx;
low[cur]=idx;//刚开始时low和时间戳肯定相同
for(int i=1;i<=n;i++){
if(e[cur][i]){//地图存在
if(num[i]==0){//num=0,即表示该点未走过
dfs(i,cur);
low[cur]=min(low[cur],low[i]);//更新当前顶点cur能访问到最早顶点的时间戳
//如果i点无法通过其他点返回到比当前点更小的时间戳,则表示cur->i这条线为割边
if(low[i]>num[cur]){
edges[k].pre=cur;
edges[k++].nxt=i;
}
}
//否则如果顶点i曾经被访问过，并且这个顶点不是当前顶点cur的父亲，则说明
//此时的i为cur的祖先,因此需要更新当前结点cur能访问到最早顶点的时间戳
else if(i!=fa){
low[cur]=min(low[cur],num[i]);
}
}
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
e[u][v]=e[v][u]=1;
}
root=1;
dfs(1,root);//从1号顶点且父节点为1处开始搜索
sort(edges,edges+k,com);
for(int i=0;i<k;i++)
printf("%d %d\n",edges[i].pre,edges[i].nxt);
return 0;
}题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。
输出格式
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^{31}-1。
输入输出样例
输入 #1复制
4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4输出 #1复制
0 2 4 3说明/提示
【数据范围】
对于 20% 的数据：1≤n≤5，1≤m≤15；
对于 40% 的数据：1≤n≤100，1≤m≤10^4；
对于 70% 的数据：1≤n≤1000，1≤m≤10^5；
对于 100% 的数据：1≤n≤10^4，1≤m≤5×10^5，1≤u,v≤n，∑w< 2^{31}，保证数据随机。对于真正 100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。
样例说明：
图片1到3和1到4的文字位置调换
题解：本题的数据将低了难度，只需要用链式前向星优化dijkstra即可。对于链式前向星，我们需要另开一个数组head（大小通常要比点的数量多1）存一类边的头的最后一个位置的编号（编号即输入的顺序），如①1->2,②1->3，head[1]=2；还需要开一个结构体数组（大小通常比边的数量多1），分别有三个元素，存边的终点，边的权重，同一个头下一条边的编号。这样就能用两个数组完成对所有边以同一个头分类开始的链存起来。在dijkstra查找边比较dis值时，改为用链式表遍历即可，其他部分均与普通dijkstra无异。
#include <stdio.h>
#include <cstring>//memset
#define INF 2147483647
#define N 10001
#define M 500010
int e[N][N],dis[N],head[N],cnt;//head 链式前向星中存边的头,cnt编号
bool book[N];
struct edge{
int to;//边的终点
int w;//权重
int nxt;//指向同一个头的边的下一条编号
}edges[M];
void add(int u,int v,int w){//创建链式前向星
edges[++cnt].to=v;
edges[cnt].w=w;
edges[cnt].nxt=head[u];
head[u]=cnt;
}
int main(){
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
memset(dis,0x3f,sizeof(dis));//将s到其它点的距离都赋为最大值
dis[s]=0;//s到本身的距离为0
for(int i=1;i<=n-1;i++){
int min=INF,u;
for(int j=1;j<=n;j++){ //找dis中未确定的最小值
if(!book[j]&&dis[j]<min){
min=dis[j];
u=j;
}
}
book[u]=true;//将dis中未确定的最小值确定
for(int j=head[u];j;j=edges[j].nxt){//根据链式前向星找出所有边的u,v,w,然后更新dis
int v=edges[j].to;
if(!book[v]&&dis[v]>dis[u]+edges[j].w)
dis[v]=dis[u]+edges[j].w;
}
}
for(int i=1;i<=n;i++)
printf("%d ",dis[i]==0x3f3f3f3f?INF:dis[i]);
return 0;
}题目描述
有一个邮递员要送东西，邮局在节点 1。他总共要送 n-1 样东西，其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。
第二行到第 (m+1) 行，每行三个整数，u,v,w，表示从 u 到 v 有一条通过时间为 w 的道路。
输出格式
输出仅一行，包含一个整数，为最少需要的时间。
输入输出样例
输入 #1复制
5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2输出 #1复制
83说明/提示
对于 30% 的数据，1≤n≤200。
对于 100% 的数据，1≤n≤10^3，1≤m≤105^，1≤u,v≤n，1≤w≤10^4，输入保证任意两点都能互相到达。
题解：本题去送快递的过程是一个以1为源点的单源最短路径直接用dijkstra就行了，但回来却成了多对一，我们并没有这个算法，而且如果直接用多源的Floyd的话肯定会超时，所以我们需要转变一下思路：因为本题是有向图，如果有x->a->b->c->1使x处回到1处时间最短，那么我们把图改成1->c->b->a->x,只需将原图颠倒一下，那么就能实现以1->x完成x回到1的最短路径。所以本题需要先按正的图跑一遍dijkstra然后再将图颠倒跑一遍dijkstra，那么整个时间就是送完n-1个货并回到1的最短时间了，所以我们可以开两个矩阵图分别存正向和反向图。本题还需要注意的是有一个坑点，那就是数据可能会出现重复的路线，而相同的路线权值却不一样的情况，所以在存图的时候，权值应该存最小的。
#include <stdio.h>
#define inf 99999999
#define Min(a,b) a<b?a:b
int e1[1010][1010],e2[1010][1010],dis[1010];//e1正向地图，e2反向地图
int n,m,cnt=0;
void dijkstra(int map[1010][1010]){
int book[1010]={0};
for(int i=1;i<=n;i++)//初始化dis
dis[i]=map[1][i];
book[1]=1;
for(int t=1;t<=n-1;t++){
int min=inf,u;
for(int i=1;i<=n;i++){
if(!book[i]&&dis[i]<min){
min=dis[i];
u=i;
}
}
book[u]=1;
for(int i=1;i<=n;i++){
if(dis[i]>dis[u]+map[u][i])
dis[i]=dis[u]+map[u][i];
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) e1[i][j]=e2[i][j]=0;
else e1[i][j]=e2[i][j]=inf;
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e1[u][v]=Min(e1[u][v],w);//本题坑点,有可能输入两次相同的路,但权值不一样 ,所以直接存权值最小的
e2[v][u]=Min(e2[v][u],w);//因为是反的地图,所以要交换i,j
}
dijkstra(e1);//正向走一遍
for(int i=1;i<=n;i++)
cnt+=dis[i];
dijkstra(e2);//反向走一遍
for(int i=1;i<=n;i++)
cnt+=dis[i];
printf("%d",cnt);
return 0;
}题目背景
2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
100→60；
Ag→Cu；
最终，他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。
题目描述
给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数 n, m, s。 第二行起 mm 行，每行三个非负整数 ui,vi,wi，表示从 ui 到 vi 有一条权值为 wi 的有向边。
输出格式
输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。
输入输出样例
输入 #1复制
4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4输出 #1复制
0 2 4 3说明/提示
样例解释请参考 数据随机的模板题。
1≤n≤10^5；
1≤m≤2×10^5；
s = 1；
1≤ui,vi≤n；
0≤wi≤10^9,
0≤∑wi≤10^9。
本题数据可能会持续更新，但不会重测，望周知。
2018.09.04 数据更新 from @zzq
题解：本题测试数据较大，需要用到链式前向星和优先队列来对dijkstra进行优化。采用优先队列即可每次都直接给出未确定的dis的最小值，省去了原来O(n)的时间复杂来遍历整个数组找最小dis，整个队列向一个二维的有序数组一样，里面存着“dis[i]”和“i”，按dis升序排列，每次都是给前面最小的dis，拿出了即要出队，为防止已出队元素重复入队，所以需要拿一个数组对已出队元素进行标记，拿到最小dis的下标就去进行比较，看是否能更新出更小的dis，产生的dis也需要入队，优先队列会自动给他排好序。
#include <bits/stdc++.h>
using namespace std;
#define INF 99999999
#define N 100010
#define M 200010
int dis[N],head[N],cnt;//head 链式前向星中存边的头,cnt编号
bool book[N];
//pair<-dis[i],i> 把-dis[i]和i合并在一起first=-dis second=i ；priority_queue默认为大项堆即整个队列降序，而给first前添负号，可以正好反过来形成小项堆
priority_queue<pair<int, int> > q;
struct edge{
int to;//边的终点
int w;//权重
int nxt;//指向同一个头的边的下一条编号
}edges[M];
void add(int u,int v,int w){//创建链式前向星
edges[++cnt].to=v;
edges[cnt].w=w;
edges[cnt].nxt=head[u];
head[u]=cnt;
}
int main(){
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
memset(dis,0x3f,sizeof(dis));//将s到其它点的距离都赋为最大值
dis[s]=0;//s到本身的距离为0
q.push(make_pair(0,s));//初始化队列 把dis[s]和s存进去
while(!q.empty()){
int u=q.top().second;//每次拿出最小dis值的下标
q.pop();//已拿出就出队
if(book[u]) continue; //防止已出队数据重复入队,用book标记
book[u]=true;//标记为已出队
for(int j=head[u];j;j=edges[j].nxt){//根据链式前向星找出所有边的u,v,w,然后更新dis
int v=edges[j].to;
if(!book[v]&&dis[v]>dis[u]+edges[j].w){
dis[v]=dis[u]+edges[j].w;
q.push(make_pair(-dis[v],v));//把更小的dis入队
}
}
}
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}