Dijkstra’s algorithm applies the greedy idea of “cutting corners”. Maintain two sets, A A A and B B B, where A A A represents the set of nodes with defined shortest paths (red) and B B represents the neighbor nodes (blue).

1. So you put starting point 1 in A, A, A, and you put all of its neighbors in B, B, and B
   
   
2. Take the node in B, B, B with the shortest distance from the starting point and put it in A, A, A, node 3, and add its neighbor to B, B, B, the distance is the distance from the starting point to that node plus the distance from that node to its neighbor.
   
   
3. So if B, B, B has the same node 2, and we take the one that’s shorter, we get rid of 2,5.
   
   
4. Similarly, put the shortest node of B, B, 2 into A, A, A, and discard the farther node (4,7).
   
   
5. Finally, we get the shortest path from the starting point to the other nodes
   
   
   
   In the above method, the priority queue can be used to find the nearest node in B, B and B each time, so that the dependency complexity can be optimized to O(M l O g(n)) O(mlog(n)) O(mlog(n)).
   
   If you want to print a path, define an array pre[] pre[] pre[] to record the precursor node, that is, whose neighbor it entered B B B, and then print recursively.

Every year in the school competition, all the finalists get a beautiful T-shirt. But every time our staff transported hundreds of clothes from the store to the venue, it was very tired! So now they want to find the shortest route from the store to the game, can you help them? Input Input contains multiple groups of data. The first line of each set of data contains two integers N and M (N<=100, M<=10000). N indicates how many roads there are in the streets of Chengdu, intersection 1 is the location of shops, intersection N is the location of sports venues, and M indicates how many roads there are in Chengdu. N=M=0 indicates that the input is complete. The next M line, each line contains three integers A,B, C (1<=A,B<=N,1<=C<=1000), indicating that there is A road between intersection A and intersection B, and it takes C minutes for our staff to cross this road. Enter a route to ensure there is at least one store to the arena. Output For each group of inputs, Output one line, representing the shortest time for the staff to walk from the store to the stadium. Sample Input 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 Sample Output 3 2 2

[B]

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 102;
struct edge { 
	int from, to, w;
	edge(int a, int b, intc) { from = a, to = b, w = c; }};struct node {
	int id, dis;
	node(int a, int b) {
		id = a, dis = b;
	}
	bool operator< (const node &a)const {
		returna.dis < dis; }};int n, m, x, y, z;
vector<edge>e[maxn];  
int dis[maxn];
bool vis[maxn];  
void dijkstra(int s) {
	dis[s] = 0;
	priority_queue<node>q; 
	q.push(node(s, dis[s])); 
	while(! q.empty()) {
		node cur = q.top(a); q.pop(a);if (vis[cur.id])continue;
		vis[cur.id] = true; 
		for (int i = 0; i < e[cur.id].size(a); i++) { edge nex = e[cur.id][i];if (vis[nex.to])continue;  
			if (dis[nex.to] > nex.w + cur.dis) {
				dis[nex.to] = nex.w + cur.dis;
				q.push(node(nex.to, dis[nex.to])); }}}}int main(a) {
	while (~scanf("%d%d", &n, &m)) {
		if (n == 0 && m == 0)break;
		for (int i = 1; i <= n; i++)e[i].clear(a);memset(dis, inf, sizeof(dis));
		memset(vis, false.sizeof(vis));
		while (m--) {
			scanf("%d%d%d", &x, &y, &z);
			e[x].push_back(edge(x, y, z));
			e[y].push_back(edge(y, x, z));
		}
		dijkstra(1);
		printf("%d\n", dis[n]);
	}
	return 0;
}
Copy the code

Problem Description One day , Kiki wants to visit one of her friends. As she is liable to carsickness , She wants to arrive at her friend’s home as soon as possible. Now give you a map of the city’s traffic route, And the stations which are near Kiki’s home so that she can take. You may suppose Kiki can change the bus at any station. Please find out the least time Kiki needs to spend. To make it easy, If the city has n bus stations,the stations will be expressed as an integer 1,2,3… n. Input There are several test cases. Each case begins with three integers n, M ands,(n<1000,m<20000,1=

Analysis: Platform number 1~ N, assuming the starting point is 0(super source point), then the distance of the point that can start directly is 0, and then the algorithm can be set.

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 1003;
struct node {
	int id, dis;
	node(int a, int b) {
		id = a, dis = b;
	}
	bool operator< (const node& a)const {
		returna.dis < dis; }};int mp[maxn][maxn], dis[maxn];
bool vis[maxn];
int n, m, e, x, y, z;
void dijkstra(a) {
	dis[0] = 0;
	priority_queue<node>q;
	q.push(node(0, dis[0]));
	while(! q.empty()) {
		node cur = q.top(a); q.pop(a);if (vis[cur.id])continue;
		vis[cur.id] = true;
		for (int i = 0; i <= n; i++) {
			if (mp[cur.id][i] == inf)continue; / / there is no way
			if (vis[i])continue;
			if (dis[i] > mp[cur.id][i] + cur.dis) {
				dis[i] = mp[cur.id][i] + cur.dis;
				q.push(node(i, dis[i])); }}}}int main(a) {
	while (~scanf("%d%d%d", &n, &m, &e)) {
		memset(mp, inf, sizeof(mp));
		memset(dis, inf, sizeof(dis));
		memset(vis, false.sizeof(vis));
		while (m--) {
			scanf("%d%d%d", &x, &y, &z);
			if (z < mp[x][y])  / / heavy edge
				mp[x][y] = z;
		}
		scanf("%d", &x);
		while (x--) { // The offset starts at 0
			scanf("%d", &y);
			mp[0][y] = 0;
		}
		dijkstra(a);if (dis[e] == inf)puts("1");
		else printf("%d\n", dis[e]);
	}
	return 0;
}
Copy the code

Address of the blogger CSDN: wzlodq.blog.csdn.net

The young explorer came to an Indian tribe. There he fell in love with the chieftain’s daughter and went to the chieftain for marriage. The chief demanded 10,000 gold coins as a dowry for his daughter. Unable to offer so many gold coins, the explorer asked the chief to lower his demand. The chief said, “Well, if you can get me the high priest’s fur coat, I can ask for 8000 gold pieces. If you can get his crystal ball, 5,000 gold pieces will do. “The explorer went to the high priest and asked him for a fur coat or a crystal ball. The high priest asked him to give him gold coins in exchange for it, or something else that he could lower the price for. The explorer then went elsewhere, and others made similar demands, either for gold or to find something else that would lower the price. But explorers don’t have to trade multiple things for one thing, because they don’t get a lower price. The explorer needs your help to marry his sweetheart for the least amount of gold. The other thing he’ll tell you is that there’s a lot of hierarchy in this tribe. There will be no direct contact of any kind, including trading, between two people whose status is beyond a certain limit. He is an outsider, so he can get away with these restrictions. But if he trades with someone lower in status, the person higher in status won’t trade with him, they think it’s an indirect contact, and vice versa. Therefore, you need to give him the best plan after considering all the circumstances. For convenience, we numbered all items starting with 1. The sheik’s promise was also considered an item, and the number was always 1. Each item has a price (P), a status level (L), and a series of alternatives (Ti) and a corresponding “preference” (Vi). If the gap between two people is larger than M, they cannot trade indirectly. You have to use these figures to figure out the minimum amount of gold an explorer needs to marry a chieftain’s daughter. The first line is two integers M, N (1 <= N <= 100), which in turn represent the status level gap limit and the total number of items. Next, the description of N items is given according to the number from small to large. The description of each item begins with three non-negative integers P, L and X (X < N), which in turn represent the price of the item, the status of the owner and the total number of substitutes. The next X line each contains two integers T and V, representing the number of the substitute and the “preferential price”, respectively. Output Indicates the minimum number of coins needed. Sample Input 1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0 Sample Output 5250

Analysis: consider items as nodes on the graph, interchange relations as edges, and find the minimum cost that is the shortest path from the starting point to a certain point. However, you also need to deal with the level limits by simply enumerating the range of levels and doing dijkstra() on each point that meets the range. For example, if the starting level is 5 and the limit is 3, the enumeration ranges are [2,5], [3,6], [4,7], [5,8] as shown in the code.

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 102;
struct node {
	int id, dis;
	node(int a, int b) {
		id = a, dis = b;
	}
	bool operator< (const node& a)const {
		returna.dis < dis; }};int n, m, x, y, z;
int mp[maxn][maxn], dis[maxn];
int lev[maxn], val[maxn];
bool tag[maxn], vis[maxn];
int dijkstra(a) {
	memset(vis, false.sizeof(vis));
	memset(dis, inf, sizeof(dis));
	priority_queue<node>q;
	dis[1] = 0;
	q.push(node(1, dis[1]));
	while(! q.empty()) {
		node cur = q.top(a); q.pop(a);if (vis[cur.id])continue;
		vis[cur.id] = true;
		for (int i = 1; i <= n; i++) {
			if(vis[i] || ! tag[i])continue; // Check whether the enumeration is in the range
			if (dis[i] > mp[cur.id][i] + cur.dis) {
				dis[i] = mp[cur.id][i] + cur.dis;
				q.push(node(i, dis[i])); }}}int rtn = inf;
	for (int i = 1; i <= n; i++) 
		if (rtn > dis[i] + val[i])  // Remember to add node weights
			rtn = dis[i] + val[i];
	return rtn;
}
int main(a) {
	scanf("%d%d", &m, &n);
	memset(mp, inf, sizeof(mp));
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &val[i], &lev[i], &x);
		while (x--) {
			scanf("%d%d", &y, &z); mp[i][y] = z; }}int ans = inf;
	for (int i = 0; i <= m; i++) {
		memset(tag, false.sizeof(tag));
		for (int j = 1; j <= n; j++) {  / / the enumeration
			if (lev[1] - m + i <= lev[j] && lev[1] + i >= lev[j])
				tag[j] = true;
		}
		ans = min(ans, dijkstra());
	}
	printf("%d\n", ans);
	return 0;
}
Copy the code

Problem Description In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary information and with the programme. A lot of students were hired to distribute these invitations among the people. Each student volunteer has assigned exactly one bus stop and he or she stays there the whole day and gives invitation to people travelling by bus. A special course was taken where students learned how to influence people and what is the difference between influencing and robbery. The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, Available in space where ‘X’ cofeo the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan. All the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees. Input The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers – the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop. Output For each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers. Sample Input 2 2 2 1 2 13 2 1 33 4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50 Sample Output 46 210

Analysis: N station m bus routes, only from the starting point to the end point (one-way), for the minimum cost of round-trip, round-trip twice, the one-way road to lane once, and then the road in turn lane once on the line. Note that large data uses adjacency matrix and long long.

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int maxn = 1000006;
struct node {
	int id, dis;
	node(int a, int b) {
		id = a, dis = b;
	}
	bool operator< (const node& a)const {
		returna.dis < dis; }};struct edge {
	int from, to, w;
	edge(int a, int b, intc) { from = a, to = b, w = c; }}; vector<edge>e[maxn];int t, n, m;
int dis[maxn];
int from[maxn], to[maxn], cost[maxn];
bool vis[maxn];
void dijkstra(int s) {
	memset(dis, inf, sizeof(dis));
	memset(vis, false.sizeof(vis));
	dis[s] = 0;
	priority_queue<node>q;
	q.push(node(s, dis[s]));
	while(! q.empty()) {
		node cur = q.top(a); q.pop(a);if (vis[cur.id])continue;
		vis[cur.id] = true;
		for (int i = 0; i < e[cur.id].size(a); i++) { edge nex = e[cur.id][i];if (vis[nex.to])continue;
			if (dis[nex.to] > cur.dis + nex.w) {
				dis[nex.to] = cur.dis + nex.w;
				q.push(node(nex.to, dis[nex.to])); }}}}int main(a) {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		for (int i = 0; i <= n; i++)e[i].clear(a);for (int i = 0; i < m; i++) {
			scanf("%d%d%d", &from[i], &to[i], &cost[i]);
			e[from[i]].push_back(edge(from[i], to[i], cost[i]));
		}
		dijkstra(1);
		ll ans = 0;
		for (int i = 1; i <= n; i++)
			ans += dis[i];
		for (int i = 0; i <= n; i++)e[i].clear(a);for (int i = 0; i < m; i++) // Reverse the path direction
			e[to[i]].push_back(edge(to[i], from[i], cost[i]));
		dijkstra(1);
		for (int i = 1; i <= n; i++)
			ans += dis[i];
		printf("%lld\n", ans);
	}
	return 0;
}
Copy the code

If the article is helpful to you, remember one key three connect ❤