Catalog

One , Single source shortest path

Two , Undirected graph actual combat

HDU 1874 Unimpeded project continued

3、 ... and , Directed graph combat

Power button 743. Network latency

One , Single source shortest path  Dijskra

Divide the points into the points that have been determined as the shortest path and the points that have not been determined , Add a new point each time to determine the shortest path , After confirmation, refresh the possible shortest path from the starting point to the remaining points according to it ,

Every time in the remaining points , Select the point closest to the starting point and add it to the set that determines the shortest path , Until all points determine the shortest circuit .

Two , Undirected graph actual combat

HDU 1874 Unimpeded project continued

subject ：

Description

Since a province has implemented the smooth flow project plan for many years , Finally, a lot of roads were built . No, it's not good if there are too many roads , Every time you go from one town to another , There are many road options to choose from , And some of them travel much shorter distances than others . It bothers pedestrians . 

Now? , Know the beginning and the end , Please calculate from the beginning to the end , The shortest distance you need to walk .
Input

This topic contains multiple sets of data , Please process to the end of the file . 
The first row of each set of data contains two positive integers N and M(0<N<200,0<M<1000), They represent the number of existing towns and the number of roads built . Cities and towns are divided into 0～N-1 Number . 
Next is M Road information . Each line has three integers A,B,X(0<=A,B<N,A!=B,0<X<10000), It means town A And town B There is a length between X A two-way road . 
The next line has two integers S,T(0<=S,T<N), They represent the starting point and the ending point respectively .
Output

For each set of data , Please output the shortest distance to walk in one line . If it doesn't exist from S To T The route of the , It outputs -1. 
Sample Input

3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output

2
-1

Too lazy , Too lazy to use adjacency table + Priority queue , Directly use the adjacency matrix and then solve it violently .

use len Record any 2 The distance between the points ,minlen Record a point to s The shortest distance .

minlen It's constantly updated , Only after visiting , namely visit become 1 after ,minlen It's true s The shortest distance , Before that, it was just its upper bound .

Code ：
 

#include<iostream>
#include<string.h>
using namespace std;

int n, m, s, t;
int con = 2000000;
int len[200][200];
int minlen[200];
int visit[200];

void dijkstra(int k)
{
	if (minlen[k] >= con)return;
	visit[k] = 1;
	for (int i = 0; i < n; i++)
	{
		if (minlen[i]>minlen[k] + len[i][k])minlen[i] = minlen[k] + len[i][k];
	}
	int l = con, key = -1;
	for (int i = 0; i < n; i++)
	{
		if (visit[i] == 0 && l>minlen[i])
		{
			key = i;
			l = minlen[i];
		}
	}
	if (key < 0)return;
	dijkstra(key);
}

int main()
{
	int a, b, x;
	while (scanf("%d%d", &n, &m) != -1)
	{
		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)len[i][j] = con;
		while (m--)
		{
			scanf("%d%d%d", &a, &b, &x);
			if (len[b][a]>x)len[a][b] = len[b][a] = x;
		}
		scanf("%d%d", &s, &t);
		for (int i = 0; i < n; i++)minlen[i] = len[i][s];
		memset(visit, 0, sizeof(visit));
		minlen[s] = 0;
		dijkstra(s);
		if (minlen[t]<con)printf("%d\n", minlen[t]);
		else printf("-1\n");
	}
	return 0;
}

But it's still very fast ,15ms  AC

There is a slight hole in this topic ,2 There is not necessarily only 1 Strip road , So update len You need to judge .

con Yes, it is 200*10000 Got ,con The function of is to ensure that if a point and s It's connected , Then the distance between them must be less than con.

So this con That is equivalent to the realization of infinity .

3、 ... and , Directed graph combat

Power button 743. Network latency

Yes n Network nodes , Marked as  1  To n.

Here's a list  times, Indicates that the signal passes through Directed Edge transfer time . times[i] = (ui, vi, wi), among  ui  Is the source node ,vi  It's the target node , wi  Is a signal from the source node to the target node time .

Now? , From a node  K  Send a signal . How long does it take for all nodes to receive signals ？ If you can't make all nodes receive signals , return  -1 .

Example 1：

Input ：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output ：2
Example 2：

Input ：times = [[1,2,1]], n = 2, k = 1
Output ：1
Example 3：

Input ：times = [[1,2,1]], n = 2, k = 2
Output ：-1
 

Tips ：

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
all (ui, vi) Right all Different from each other （ namely , Without duplicate edges ）

// Input edge set {
   {1,2}{1,3}{2,3}}, Output adjacency table {1:{2,3},2:{3}}
map<int, vector<int>> edgeToAdjaList(vector<vector<int>>& v)
{
	map<int,vector<int>> ans;
	for (auto &vi : v) {
		ans[vi[0]].push_back(vi[1]);
	}
	return ans;
}
// Enter the weighted edge set , Output edge and weight mapping 
map<pair<int, int>, int> edgeToValueMap(vector<vector<int>>& v)
{
	map<pair<int, int>, int>m;
	for (auto& vi : v) {
		m[{vi[0], vi[1]}] = vi[2];
	}
	return m;
}

struct Node
{
	int id;
	int len;
};
class cmp
{
public:
	bool operator()(Node a, Node b)
	{
		return a.len > b.len;
	}
};

class Solution {
public:
	int networkDelayTime(vector<vector<int>>& times, int n, int k) {
		map<int, int>m;
		for (int i = 1; i <= n; i++)m[i] = INT_MAX;
		map<int, vector<int>> adja = edgeToAdjaList(times);
		map<pair<int, int>, int> value = edgeToValueMap(times);
		priority_queue< Node, vector< Node>, cmp>que;
		map<int, int>visit;
		que.push({ k,0 });
		m[k] = 0;
		while (!que.empty())
		{
			Node nod = que.top();
			que.pop();
			if (visit[nod.id])continue;
			visit[nod.id] = 1;
			for (auto& vi : adja[nod.id]) {
				if (nod.len + value[{nod.id, vi}] < m[vi]) {
					que.push({ vi, m[vi] = nod.len + value[{nod.id, vi}] });
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (m[i] == INT_MAX)return -1;
			ans = max(ans, m[i]);
		}
		return ans;
	}
};