Shortest path topic

shortest path

Floyd-Warshall Algorithm

purpose ： Find the shortest path of multiple sources （ That is, the shortest circuit between any two points ）

Pictured above , We need the shortest distance between different cities , You can list a simple distance matrix

And then according to a->b If the distance is less than （a->c）+（c->b） Distance of , Will a->b Replace the distance of with （a->c）+（c->b） The distance logic of .
The core code is as follows ：

for(k=1;k<=n;k++)  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
	if(e[i][j]>e[i][k]+e[k][j])  
		e[i][j]=e[i][k]+e[k][j];  

The point to note here is , In the outermost for Of the statement k, Be sure to put it in the middle of the judgment statement .

The disadvantage is that it will cover the original side length , If you need to perform multiple operations , The original side length cannot be retrieved , And negative weight cannot be calculated , Code time complexity O(n³).

Dijkstra Algorithm

The characteristic of the dichhester algorithm is , It increases the vis Array , For relaxation operation , The relaxation operation is also dijkstra The most striking feature , It can greatly reduce the time complexity , Added dis Array , To determine the distance , Instead of covering the original side length , After the operation, the original side length array can still be kept unchanged .
Dijkstra The algorithm is greedy , First save the distance from the starting point to all points to find the shortest , Then relax once and find the shortest , The so-called relaxation operation is , Go through it and see if it will be closer to the shortest point just found as a transfer station , If it's closer, update the distance , In this way, after finding all the points, the shortest distance from the starting point to all other points is saved .


Operate according to such logic
The code example is as follows

void dijk(int s) {
    // Calculate all points to s The shortest distance , Deposit in dis In the array 
	memset(dis, 0x3f, sizeof(dis));// Set the distance to maximum 
	memset(vis, 0, sizeof(vis));// Initialize to all unrelaxed States 
	dis[s] = 0;// The distance to oneself is 0
	while (1) {
    
		int k = 0;// Find the nearest unrelaxed node 
		for (int j = 1;j <= n;j++) {
    
			if (!vis[j] && dis[j] < dis[k])
				k = j;// Set the nearest unrelaxed node to k
		}
		if (!k)return;// If there are no recently unrelaxed nodes , Explain all slack , end 
		vis[k] = 1;// Relaxation complete 
		for (int j = 1;j <= n;j++) {
    
			if (dis[j] > dis[k] + map[k][j]) {
    // Judge , replace dis length 
				dis[j] = dis[k] + map[k][j];
			}
		}
	} 
}

The disadvantage is that negative weight cannot be calculated , Code time complexity O(n²), Using chained forward stars or priority queues for optimization can be optimized as O(nlogn).

Bellman-Ford Algorithm

This algorithm is better than dijkstra It's easier , Reduce the operation of determining relaxation , Relax each point repeatedly , Each relaxation operation , There will be some vertices that have found their shortest path , That is, the shortest path of these vertices “ Estimated value ” Turn into “ Determinate value ”. The advantages are obvious , Negative weight can be calculated , But at the same time, the time complexity will also increase .

Code example ：

for(int k = 1 ; k <= n - 1 ; k ++)
{
    
    for(int i = 1 ; i < m ; i ++)
    {
    
        if(dis[v[i]] > dis[u[i]] + w[i])
            dis[v[i]] = dis[u[i]] + w[i] ;
    }
}

Title Example ：

President Dongdong wants to marry the Sheikh's daughter , But the chief asked him to give a certain amount of money as a dowry . Besides money , The chief also allowed to use some items of other people in the tribe plus a little money as a dowry . Other people's items can also be obtained by specifying some items of other people plus some money . But everyone in the tribe has a level . The level of people involved in the whole transaction process can only be within a limited difference . Ask the president how much money Dongdong needs at least to marry the Sheikh's daughter . Suppose everyone has only one item .

Input
The first line of input is two integers M,N（1 <= N <= 100）, In turn, it represents the status level gap limit and the total number of items . Next, according to the number from small to large, it gives N A description of an object . The description of each item begins with three non negative integers P、L、X（X < N）, Show the price of the item in turn 、 Master's rank and total number of substitutes . Next X Each line contains two integers T and V, The number of the substitute and " Favorable Price ".

Output
Output the minimum number of gold 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

example ： The difference between the highest and lowest grades shall not exceed 1, common 4 Items The Sheikh's daughter Grade 3 Ask for cash 10000 element Or items of a +8000 element Or B's items +5000 element Items of a Grade 2 Ask for cash 1000 element Or C items +200 element B's items Grade 2 Ask for cash 3000 element Or C items +200 element C's items Grade 2 Ask for cash 50 element In this case , The minimum cost plan is ： Buy C's things （50） Change B's things （+200） For the Sheikh's daughter （+5000） altogether 5250 element .

Code example ：

#include<iostream>
#include<cstring>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdio>
#include<set>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn = 1000;
ll e[1020][1020];
int vis[1020], dis[1020];
ll lv[10000],temp,minn;
int n, m, t, x;
void dijk(int s, int l, int r) {
    
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	dis[s] = 0;
	while (1) {
    
		int k=-1,minn=0x3f3f3f3f;
		for (int j = 0;j <= n;j++) {
    
			if (!vis[j] && dis[j] < minn) {
    
				k = j;
				minn = dis[j];
			}
		}
		if (k==-1)return;
		vis[k] = 1;
		for (int j = 0;j <= n;j++) {
    
			if (lv[j] >= l && lv[j] <= r) {
    
				if (dis[j] > dis[k] + e[k][j]) {
    
					dis[j] = dis[k] + e[k][j];
				}
			}
		}
	}
}
void Init() {
    
	memset(e, 0x3f3f3f3f, sizeof e);
	for (int i = 1;i <= m;i++) {
    
		e[i][i] = 0;
	}
}
void input() {
    
	cin >> m >> n;
	for (int i = 1;i <= n;i++) {
    
		cin >> e[0][i] >> lv[i] >> t;
		for (int j = 1;j <= t;j++) {
    
			cin >> x;
			cin >> e[x][i];
		}
	}
}
int main() {
    
	Init();
	input();
	int ans = 0x3f3f3f3f;
	for (int i = lv[1] - m;i <= lv[1];i++) {
    
		dijk(0, i, i + m);
		ans = min(dis[1], ans);
	}
	cout << ans;
}