蓝桥杯国赛——路径（最短路）

水深无声 2021-07-17 01:34 489阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]

## 思路 ##

很明显的最短路，建完图后，直接跑dijkstra即可，细节见代码。

## 答案：10266837 ##

## Code ##

#include<iostream>
    #include<queue>
    #include<memory.h>
    using namespace std;
    typedef long long ll;
    
    const int Max = 1e6 + 5;
    
    int u[Max], v[Max], w[Max];
    int g = 0, first[Max], nex[Max];
    
    struct node
    { 
    	int n, w;
    	bool operator<(const node& a)const
    	{ 
    		return w > a.w;
    	}
    	node(int a, int b)
    	{ 
    		n = a;
    		w = b;
    	}
    };
    
    ll dis[Max], b[Max];
    priority_queue<node> que;
    
    void add(int a, int b,int c)
    { 
    	u[++g] = a;
    	v[g] = b;
    	w[g] = c;
    	nex[g] = first[a];
    	first[a] = g;
    }
    
    ll gcd(ll a, ll b)
    { 
    	if (a == 0)return b;
    	return gcd(b%a, a);
    }
    
    ll lcm(ll a, ll b)
    { 
    	return a * b / gcd(a, b);
    }
    
    int main()
    { 
    
    	memset(first, -1, sizeof(first));
    	memset(dis, 0x7f, sizeof(dis));
    	for (int i = 1;i <= 2021;i++)
    	{ 
    		for (int j = i + 1;j - i <= 21 && j <= 2021;j++)
    		{ 
    			add(i, j, lcm(i, j));
    			add(j, i, lcm(i, j));
    		}
    	}
    	que.push(node(1,0));
    	dis[1] = 0;
    	while(!que.empty())
    	{ 
    		node no = que.top();
    		que.pop();
    		if (b[no.n])continue;
    		dis[no.n] = no.w;
    		b[no.n] = 1;
    		for (int i = first[no.n];i != -1;i = nex[i])
    		{ 
    			if (b[v[i]])continue;
    			if (dis[u[i]] + w[i] < dis[v[i]])
    			{ 	
    				dis[v[i]] = dis[u[i]] + w[i];
    				que.push(node(v[i],dis[u[i]]+w[i]));
    			}
    		}
    	}
    	cout << dis[2021];
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/9ddd7a78274649f9a4b5b3b1d35e4a4f.png