最短路,不知道哪里错了
  • 板块P2083 找人
  • 楼主Exile_Code
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/18 21:57
  • 上次更新2024/3/19 12:09:41
查看原帖
最短路,不知道哪里错了
819682
Exile_Code楼主2024/3/18 21:57
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <math.h>
#include <functional>
#include <unordered_map>
#include <unordered_set>


#define ull		        unsigned long long 
#define ll              long long
#define pii             pair<ull ,ull>
#define cy              cout<<"YES"<<endl
#define cn              cout<<"NO"<<endl
#define forn(i,begin,end,add)	for(ll (i)=(begin);(i)<=(end);(i)+=(add))	//begin是i的起始,end是i的终止,add是每次加的大小
#define rforn(i,begin,end,sub)  for(ll (i)=(end);(i)>=(begin);(i)-=(sub))	//r是倒序遍历
#define vv              vector
#define inf32           INT32_MAX/2
#define inf64           INT64_MAX/2
#define LD              double
#define PI              acos(-1)
#define debug(a,b)		cout<<a<<b
#define eps				1e-12


const int N = 2e5 + 10;
ll T;

int mod = 998244353;


void solve() {

	int n; cin >> n;
	int m; cin >> m;
	int v, x, y;
	cin >> v >> x >> y;

	vv<vv<pii>>e((n + 1) * (m + 1) + 1);
	vv<ll>d((n + 1) * (m + 1) + 1, inf64);
	vv<int>vis((n + 1) * (m + 1) + 1);

	forn(i, 1, n - 1, 1) {
		e[i].push_back({ i + 1,0 });
		e[i + 1].push_back({ i,0 });
	}

	forn(i, 1, n, 1) {
		forn(j, 1, m, 1) {
			int a, b; cin >> a >> b;
			int now = (i - 1) * m + j;
			int to = (a - 1) * m + b;
			e[now].push_back({ to,abs(b - j) * v });
			//e[to].push_back({ now,abs(b - j) * v });
		}
	}

	priority_queue<pair<ll, int>>q;

	forn(i, 1, n, 1)
		d[i] = 0;

	int s = 1;
	d[s] = 0; q.push({ 0,s });
	while (q.size()) {
		auto t = q.top();
		q.pop();
		int u = t.second;
		if (vis[u])
			continue;

		vis[u] = 1;

		for (auto ed : e[u]) {
			int v = ed.first, w = ed.second;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				q.push({ -d[v],v });
			}
		}
	}

	int end = (x - 1) * m + y;

	if (d[end] == inf64) {
		cout << "impossible" << endl;
	}
	else {
		cout << d[end] << endl;
	}
}
int main() {


	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	T = 1;
	//cin >> T;
	while (T--)
		solve();


}

2024/3/18 21:57
加载中...