MELE3 - MELE3

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> ke[50050];
int n, m;
int F[50050];

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;++i) {
		int u, v;
		scanf("%d%d", &u, &v);	
		ke[u].push_back(v);
		ke[v].push_back(u);
	}
	queue<int> q;
	memset( F, 0x1f, sizeof(F));
	F[1] = 0;
	q.push(1);
	while(!q.empty()) {
		int u = q.front();
		int t = F[u];
		q.pop();
		for(int k=0;k<ke[u].size();++k) {
			int v = ke[u][k];
			int len = u - v;
			if(len < 0) len = -len;
			if(u < v) {
				int z = t;
				if(z % (2*len) != 0) 
					z = (z / (2*len) + 1) * 2 * len;
				if(F[v] > z + len) {
					F[v] = z + len;
					q.push(v);	
				}
			}
			else {
				int z = t;
				if(z % (2*len) != len) {
					if(z % (2*len) < len) {
						z = z / (2*len) * (2*len) + len;	
					}
					else {
						z = (z / (2*len) + 1) * (2*len) + len;	
					}
				}	
				if(F[v] > z + len) {
					F[v] = z + len;
					q.push(v);	
				}
			}
		}	
	}
	cout << F[n] * 5 << endl;
	// system("pause");
	return 0;	
}

Download