网站建设中啥意思,株洲关键词优化费用,重庆模板网站建设,wordpress怎样更换主题宣传一下算法提高课整理 —
CSDN个人主页#xff1a;更好的阅读体验 — 题目传送门点这里
题目描述
德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪#xff01;#xff01;#xff01;
他们的德克萨斯长角牛吃起来不错#xff0c;可是它们并不是很擅长生产富…宣传一下算法提高课整理 —
CSDN个人主页更好的阅读体验 — 题目传送门点这里
题目描述
德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪
他们的德克萨斯长角牛吃起来不错可是它们并不是很擅长生产富含奶油的乳制品。
农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任以减轻德克萨斯人忍受酷暑的痛苦。
John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。
这些路线包括起始点和终点一共有 T 个城镇为了方便标号为 1 到 T。
除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。
每条道路有一个通过费用包括油费过路费等等。
给定一个地图包含 C 条直接连接 2 个城镇的道路。
每条道路由道路的起点 Rs终点 Re 和花费 Ci 组成。
求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。
输入格式
第一行: 444 个由空格隔开的整数: T,C,Ts,TeT,C,T_s,T_eT,C,Ts,Te;
第 222 到第 C1C1C1 行: 第 i1i1i1 行描述第 iii 条道路包含 333 个由空格隔开的整数: Rs,Re,CiR_s,R_e,C_iRs,Re,Ci。
输出格式
一个单独的整数表示从 TsT_sTs 到 TeT_eTe 的最小总费用。
数据保证至少存在一条道路。
数据范围
1≤T≤2500,1≤T≤2500,1≤T≤2500, 1≤C≤6200,1≤C≤6200,1≤C≤6200, 1≤Ts,Te,Rs,Re≤T,1≤T_s,T_e,R_s,R_e≤T,1≤Ts,Te,Rs,Re≤T, 1≤Ci≤10001≤C_i≤10001≤Ci≤1000
样例输入
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样例输出
7思路
我们先抽象出图 题目的大致意思是给定一个无向图并给定起点和终点求其最短路径。
这就基本上是一道模板题了作者在这里是用朴素Dijkstra算法写的。当然有些同学为了节省时间可能会用SPFA。但这是个正权图如果出题人非常敬业 邪恶 的话就会把SPFA卡掉。
所以在OI赛制下正权图的最短路尽量还是用Dijkstra除非时间限制真的不够用。
因为本题的点数和边数都不是很大所以原则上无论用邻接表或者邻接矩阵都是可以存下的。
算法时间复杂度
假定这里n表示点数m表示边数则
朴素Dijkstra算法的时间复杂度是O(n2)O(n^2)O(n2) SPFA算法的时间复杂度一般是O(m)O(m)O(m)最坏情况下是O(nm)O(nm)O(nm) 堆优化Dijkstra的时间复杂度是O(mlogn)O(m \log n)O(mlogn)
AC Code CCC #include iostream
#include cstringusing namespace std;const int N 2520;int n, m, st, ed;
int g[N][N]; // 邻接矩阵存图
int dist[N]; // 存最短距离
bool f[N]; // 找过的点的集合int dijkstra(int st, int ed) // Dijkstra算法
{memset(dist, 0x3f, sizeof(dist)); // 初始化dist数组dist[st] 0; // 起点距离设置为0for (int i 1; i n; i ){int t -1;for (int j 1; j n; j )if (!f[j] (t -1 || dist[j] dist[t]))t j; // 找到当前与源点距离最短的那个点f[t] 1; // 将该点标记上表示这个点已经找过了for (int j 1; j n; j )dist[j] min(dist[j], dist[t] g[t][j]); // 用这个点更新源点与其他点的最短距离}return dist[ed]; // 返回st-ed的最短距离
}int main()
{memset(g, 0x3f, sizeof(g)); // 初始化邻接矩阵int a, b, c;scanf(%d%d, n, m);scanf(%d%d, st, ed);while (m -- ){scanf(%d%d%d, a, b, c);g[a][b] min(g[a][b], c);g[b][a] min(g[b][a], c); // 因为可能有重边所以需要取最小值}int res dijkstra(st, ed);printf(%d\n, res); // 数据保证有解故不需要判断return 0;
}最后如果觉得对您有帮助的话点个赞再走吧
