目录

P1629 邮递员送信

 P3371 【模板】单源最短路径（弱化版）

 P4779 【模板】单源最短路径（标准版）

 P1359 租用游艇

 P2910 [USACO08OPEN]Clear And Present Danger S

P1339 [USACO09OCT]Heat Wave G

P1629 邮递员送信

思路分析：

  这道题我采用的是Bellman-Ford算法，第一步求从源点1到其他点的距离直接套用模板就行。但是第二步需要回到源点1，由于题目说所有的路线都是单行线，因此不能够原路返回。其实有个比较笨的方法，就是把除源点之外的点，全部都当作一次源点，然后求出到点1的最短路径，但那样的话会比较麻烦。我们不妨把问题转换一下，例如点4回到点1的最短路径是8，那么如果把所有路的方向全部变为i相反的，那么1到4的距离也仍然是8.因此这里我们可以把所有边的起点和终点反过来，然后求出源点1到其他点的距离，也就是求出了其他点在原方向中回到源点1的最短路径。

代码实现： 

#includeusing namespace std;int dis[100010];int u[100010],v[1000010],w[1000010];int n,m;void ford1()//按照原图走一遍，求出源点1到其他点的最短路径{ for(int i=1;i<=n;i++) { dis[i]=999999; } dis[1]=0; for(int i=1;i<=n-1;i++) for(int j=1;j<=m;j++) if(dis[u[j]]+w[j]>n>>m; for(int i=1;i<=m;i++) { cin>>u[i]>>v[i]>>w[i]; } int sum1=0; ford1(); for(int i=1;i<=n;i++) sum1+=dis[i]; for(int i=1;i<=n;i++) cout<

 P3371 【模板】单源最短路径（弱化版）

思路分析： 

   这道题采用SPFA算法。先用邻接表存储整个图，然后定义一个队列，将出发的点存入队列当中，然后找寻这个点的所有出边所对应的点，并对这些点进行松弛操作，如果这个点没有在队列中的话，就把它放到队尾，然后将当前首结点出队，继续遍历队列中的下一个元素。当队列为空的时候，算法结束。

代码实现： 

#include#include#includeusing namespace std;long long dis[10100];int book[10100];int que[700010],head=1,tail=1;int first[510000],nxt[510000];long long n,m,s;int u[510000],v[510000],w[510000];int main(){ cin>>n>>m>>s; for(int i=1;i<=n;i++) {dis[i]=pow(2,31)-1; } dis[s]=0; for(int i=1;i<=m;i++)//采用邻接表存储图 { cin>>u[i]>>v[i]>>w[i]; nxt[i]=first[u[i]]; first[u[i]]=i; } que[tail]=s;//将第一个结点存入到队列当中 tail++; book[s]=1;//标记第一个结点已经在队列当中 while(headdis[u[k]]+w[k]) { dis[v[k]]=dis[u[k]]+w[k]; if(!book[v[k]])//判断出边所对应的结点是否在队列当中 { que[tail]=v[k]; tail++; book[v[k]]=1; } } k=nxt[k];//继续遍历下一跳出边 } book[que[head]]=0; head++; } for(int i=1;i<=n;i++) cout<

 P4779 【模板】单源最短路径（标准版）

思路分析： 

    这道题如果还用spfa的话就会超时。因此这里采用堆优化迪杰斯特拉算法。我们知道，普通迪杰斯特拉算法，是从还没找过的点中找到离当前点最近的那个点，然后对那个点的所有出边进行松弛操作。但是这里我们运用前向星来存储整个图，然后定义优先队列，也就是说每次入队的时候，都按照从原点到其他点的距离从小到大存储，那么我们每次取的点就是离当前点最近的那个点。

 代码实现：

#includeusing namespace std;int n,m,s,idx;int dis[100010],book[100010],head[100010],cnt=0;struct edge{ int to; int v; int next;}edge[500010];struct tmp {//自定义优先队列的排序方式，按照权值从小到大排 int idx; int v; bool operator<(const tmp &x) const { return x.v < v; }}; priority_queue q;//定义一个优先队列void add(int a, int b,int c)//采用前向星来存储真个图{ cnt++; edge[cnt].v=c; edge[cnt].to=b; edge[cnt].next=head[a]; head[a]=cnt;}void di(){ while(q.size()) { idx=q.top().idx; q.pop(); if(book[idx])continue; book[idx]=1; for(int i=head[idx];i;i=edge[i].next) { int a=idx,b=edge[i].to,c=edge[i].v; if(dis[b]>dis[a]+c) { dis[b]=dis[a]+c; if(book[b]==0)q.push({b,dis[b]}); } } }}int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++) { int u,v,w; cin>>u>>v>>w; add(u,v,w); } for(int i=1;i<=n;i++) dis[i]=1000000010; dis[s]=0; q.push({s,0}); di(); for(int i=1;i<=n;i++) { cout<

 P1359 租用游艇

思路分析： 

  这道题目采用dp的思想，枚举从倒数第二个点开始到最前面的点，然后从当前点的下一个点，一直到最后一个点，不断更新当前点到最后一个点N的最小值。 dp[i]=min(dp[i],a[i][j]+dp[j]);当然这道题也可以用弗洛伊德算法来写，利用邻接矩阵存图，然后枚举每个点，然后遍历整张图，更新每个点到最后一个点的最短路径。

 代码实现（dp算法）：

#includeusing namespace std;int dp[300];int a[300][300];int n;int main(){ cin>>n; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) cin>>a[i][j]; memset(dp,10010,sizeof(dp)); dp[n]=0; for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) dp[i]=min(dp[i],a[i][j]+dp[j]); cout<

（floyd算法）： 

#includeusing namespace std;int a[1000][1000];int min(int a,int b){ if(a>n; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { if(i==j) { a[i][j]=0; continue; } int far; cin>>far; a[i][j]=far; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=min(a[i][j],a[i][k]+a[k][j]); cout<

 P2910 [USACO08OPEN]Clear And Present Danger S

题意翻译

农夫约翰正驾驶一条小艇在牛勒比海上航行．

海上有 N(1leq Nleq 100)N(1≤N≤100) 个岛屿，用 11 到 NN 编号．约翰从 11 号小岛出发，最后到达 NN 号小岛．

一张藏宝图上说，如果他的路程上经过的小岛依次出现了 A_1,A_2,dots ,A_M(2leq Mleq 10000)A1​,A2​,…,AM​(2≤M≤10000) 这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数 D_{i,j}(0leq D_{i,j}leq 100000)Di,j​(0≤Di,j​≤100000) 来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？

输入输出格式

输入格式：

第一行：两个用空格隔开的正整数 NN 和 MM。

第二到第 M+1M+1 行：第 i+1i+1 行用一个整数 A_iAi​ 表示 FJ 必须经过的第 ii 个岛屿

第 M+2M+2 到第 N+M+1N+M+1 行：第 i+M+1i+M+1 行包含 NN 个用空格隔开的非负整数分别表示 ii 号小岛到第 1dots N1…N 号小岛的航线各自的危险指数。保证第 ii 个数是 00。

输出格式 第一行：FJ 在找到宝藏的前提下经过的航线的危险指数之和的最小值。

说明 这组数据中有三个岛屿，藏宝图要求 FJ 按顺序经过四个岛屿：11 号岛屿、22 号岛屿、回到 11 号岛屿、最后到 33 号岛屿。每条航线的危险指数也给出了：航路(1,2),(2,3),(3,1)(1,2),(2,3),(3,1) 和它们的反向路径的危险指数分别是 5,2,15,2,1。

FJ 可以通过依次经过 1,3,2,3,1,31,3,2,3,1,3 号岛屿以 77 的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求 (1,2,1,3)(1,2,1,3)。我们避开了 11 号和 22 号岛屿之间的航线，因为它的危险指数太大了。

注意：测试数据中 aa 到 bb 的危险指数不一定等于 bb 到 aa 的危险指数！

   这道题目很简单，直接套用floyd算法模板，唯一需要注意的就是需要定义一个island数组来存储需要经过的小岛，把两个岛之间的最短路径加起来然后输出即可。

代码实现： 

#includeusing namespace std;int map1[200][200];int island[10010];int n,m;int sum;int main(){ cin>>n>>m; for(int i=1;i<=m;i++) cin>>island[i]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>map1[i][j]; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map1[i][j]=min(map1[i][j],map1[i][k]+map1[k][j]); for(int i=1;i

P1339 [USACO09OCT]Heat Wave G

思路分析： 

   这道题采用Bell-Ford算法，用数组来存图。总共循环顶点数量n-1次，然后遍历所有边，对所有边都进行松弛操作。需要注意的是这里是无向图，所以应该采用两次算法，第一次正常遍历，第二次是遍历反向图，也就是每条边的起点和终点互换。

代码实现： 

#includeusing namespace std;int dis[3000];int u[7000],v[7000],w[7000];int check;int main(){ int n,m,s,t; cin>>n>>m>>s>>t; for(int i=1;i<=m;i++) { cin>>u[i]>>v[i]>>w[i]; } memset(dis,9999,sizeof(dis)); dis[s]=0; for(int i=1;i<=n-1;i++) { check=0; for(int j=1;j<=m;j++) { if(dis[v[j]]>dis[u[j]]+w[j]) {dis[v[j]]=dis[u[j]]+w[j]; check=1; } if(dis[u[j]]>dis[v[j]]+w[j]) {dis[u[j]]=dis[v[j]]+w[j]; check=1; } } if(!check)break; } cout<