美团2018年CodeM大赛-初赛B轮 B 配送

题意

题解

对于每个任务，只要从上个任务的终点出发即可。

时间、地点很少，可以算出每个地点-时间的最小花费。

以题目描述的起点终点起始结束时间建图，很暴力的跑最短路即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define rep(i, a, b) for(int i=(a); i<(b); i++)

#define sz(a) (int)a.size()

#define de(a) cout << #a << " = " << a << endl

#define dd(a) cout << #a << " = " << a << " "

#define all(a) a.begin(), a.end()

#define endl "\n"

typedef long long ll;

typedef pair<int, int> pii;

typedef vector<int> vi;

//---

const int inf = 2e9;

int n, m, k;

struct Task {

	int pos;

	string tim;

	bool operator < (const Task &c) const {

		return tim < c.tim;

	}

}task[11];

struct Edge {

	int v, p;

	string st, ed;

	Edge(int v, int p, string st, string ed) : v(v), p(p), st(st), ed(ed) {}

};

vector<Edge> g[111];

map<string, int> dis[111];

void dij(int pos, string tim) {

	rep(i, 1, k+1) dis[i].clear();

	dis[pos][tim] = 0;

	priority_queue<pair<int, pair<int, string> > > que;

	que.push(mp(0, mp(pos, tim)));

	while(!que.empty()) {

		auto u = que.top(); que.pop();

		int d = -u.fi;

		pos = u.se.fi; tim = u.se.se;

		if(d != dis[pos][tim]) continue;

		for(auto i : g[pos]) {

			int v = i.v, p = i.p;

			int t = dis[pos][tim] + p;

			if(tim < i.st && (!dis[v].count(i.ed) || dis[v][i.ed] > t)) {

				dis[v][i.ed] = t;

				que.push(mp(-t, mp(v, i.ed)));

			}

		}

	}

}

int main() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cin >> n >> m >> k;

	rep(i, 0, n) {

		string s1, s2;

		cin >> task[i].pos >> s1 >> s2;

		task[i].tim = s1 + " " + s2;

	}

	sort(task, task+n);

	rep(i, 0, m) {

		int u, v, p;

		string st, ed;

		cin >> u >> v >> p >> st >> ed;

		rep(j, 1, 8) {

			string t1 = "2018.07.0" + to_string(j) + " " + st;

			string t2 = "2018.07.0" + to_string(j) + " " + ed;

			g[u].pb(Edge(v, p, t1, t2));

		}

	}

	int pos = 1, ans = 0;

	string tim = "2018.06.30 23:59:59.999";

	rep(i, 0, n) {

		dij(pos, tim);

		int res = inf;

		for(auto j : dis[task[i].pos]) {

			if(j.fi < task[i].tim) res = min(res, j.se);

			else break;

		}

		if(res == inf) {

			ans = inf;

			break;

		}

		ans += res;

		pos = task[i].pos;

		tim = task[i].tim;

	}

	if(ans == inf) ans = -1;

	cout << ans << endl;

	return 0;

}

巴特西

美团2018年CodeM大赛-初赛B轮 B 配送（最短路）

美团2018年CodeM大赛-初赛B轮 B 配送

题意

题解

代码

最新文章

热门文章