Submission #1351137
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <chrono> #include <queue> #include <functional> using namespace std; //タイマー class Timer { chrono::high_resolution_clock::time_point start, end; double limit; public: Timer() { start = chrono::high_resolution_clock::now(); } Timer(double l) { start = chrono::high_resolution_clock::now(); limit = l; } double getTime() { end = chrono::high_resolution_clock::now(); return chrono::duration<double>(end - start).count(); } bool Over() { if (getTime() > limit) { return true; } return false; } void setLimit(double l) { limit = l; } void setStart() { start = chrono::high_resolution_clock::now(); } }; #define SIZE 50 #define LIMIT 9.0 #define INF 1e7 int H, W, K, sr, sc; int N; vector<vector<int>>DIST[SIZE][SIZE]; vector<vector<int>>status; vector<vector<int>>cost; int h[] = { 0,1,0,-1 }; int v[] = { -1,0,1,0 }; vector<vector<int>>MAP; bool range_over(pair<int, int>pos) { if (pos.first < 0 || pos.first >= H || pos.second < 0 || pos.second >= W)return true; return false; } void dijkstra(pair<int,int> s) { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { status[i][j] = 0; cost[i][j] = INF; } } cost[s.first][s.second] = 0; status[s.first][s.second] = 1; priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>>U; U.push(make_pair(cost[s.first][s.second], s)); while (!U.empty()) { //探索が終わってない中でコスト最小の点 pair<int,int> u = U.top().second; U.pop(); if (status[u.first][u.second] == -1) continue; status[u.first][u.second] = -1; //コスト最少の点を探る for (int i = 0; i < 4; i++) { pair<int, int>nu; nu.first = u.first + v[i]; nu.second = u.second + h[i]; if (range_over(pair<int, int>(nu.first, nu.second)))continue; if (MAP[nu.first][nu.second])continue; if (status[nu.first][nu.second] != -1) { if (cost[nu.first][nu.second] > cost[u.first][u.second] + 1) { cost[nu.first][nu.second] = cost[u.first][u.second] + 1; status[nu.first][nu.second] = 1; U.push(make_pair(cost[nu.first][nu.second], pair<int, int>(nu.first, nu.second))); } } } } } string dir[] = { "D","L","U","R" }; string pathfind(int r, int c, int r2, int c2) { string path = ""; while (r != r2 || c != c2) { for (int i = 0; i < 4; i++) { int nr = r2 + v[i]; int nc = c2 + h[i]; if (range_over(pair<int, int>(nr, nc)))continue; if (MAP[nr][nc])continue; if (DIST[r][c][nr][nc] == DIST[r][c][r2][c2] - 1) { path += dir[i]; r2 = nr; c2 = nc; break; } } } return path; } struct FOOD{ int r, c; int F, D; FOOD() {} FOOD(int r_, int c_, int F_, int D_) { r = r_, c = c_, F = F_, D = D_; } }; vector<FOOD>foods; struct STATE { int score; int time; pair<int, int>pos; vector<int>order; int loss; STATE(int score_, int time_, pair<int, int>pos_, vector<int>&order_, int loss_) { score = score_, time = time_, pos = pos_, loss = loss_; order = order_; } bool operator<(const STATE&right) const { return loss < right.loss; //return score < right.score; } }; vector<int>next_order(vector<int>vec, int j, int turn) { vec[j] = turn; return vec; } vector<int> solve(){ Timer tmr(LIMIT); vector<int>res(N); int maxscore = 0; int width = 1; vector<priority_queue<STATE>>stats(SIZE*SIZE); stats[0].push(STATE(0, -1, make_pair(sr, sc), vector<int>(N), 0)); //vector<vector<STATE>>stats(SIZE*SIZE); //stats[0].push_back(STATE(0,-1, make_pair(sr, sc), vector<int>(N), 0)); int max_turn = 0; int turn; int cnt = 0; while (!tmr.Over()) { turn = 0; for (int k = 0; k < 1500;k++) { //if (turn && stats[turn].empty())break; for (int i = 0; i < width; i++) { if (stats[turn].empty())break; //sort(stats[turn].begin(), stats[turn].end()); /*if (stats[turn].size() > 10*2500/(max_turn+1)) { for (int k = stats[turn].size() - 1; k >= 10 * 2500 / (max_turn + 1); k--)stats[turn].erase(stats[turn].begin() + k); }*/ //STATE nowState = stats[turn][0]; //stats[turn].erase(stats[turn].begin()); STATE nowState = stats[turn].top(); stats[turn].pop(); if (nowState.score > maxscore) { maxscore = nowState.score; res = nowState.order; } int sumD = 0; for (int j = 0; j < N; j++) { if (nowState.order[j])continue; sumD += foods[j].D; } if (stats[turn + 1].size() > 1000)continue; for (int j = 0; j < N; j++) { FOOD food = foods[j]; int dist = DIST[nowState.pos.first][nowState.pos.second][food.r][food.c]; int time = nowState.time + dist; int score = food.F - food.D * time; int loss = -(sumD - food.D) * time; if (time > K)continue; if (score <= 0)continue; if (nowState.order[j])continue; stats[turn + 1].push(STATE(nowState.score + score, time, pair<int, int>(food.r, food.c), next_order(nowState.order, j, turn + 1), loss)); } } turn++; max_turn = max(max_turn, turn); } cnt++; //cerr << cnt << endl; } cerr << cnt << endl; cerr << maxscore << endl; return res; } int main() { cin >> H >> W >> K; cin >> sr >> sc; sr--; sc--; MAP.resize(H); for (int i = 0; i < H; i++) { MAP[i].resize(W); for (int j = 0; j < W; j++) { char c; cin >> c; if (c == '#')MAP[i][j] = 1; } } status.resize(SIZE, vector<int>(SIZE)); cost.resize(SIZE, vector<int>(SIZE)); dijkstra(pair<int, int>(sr, sc)); DIST[sr][sc] = cost; cin >> N; foods.resize(N); for (int i = 0; i < N; i++) { int r, c, F, D; cin >> r >> c >> F >> D; r--; c--; foods[i] = FOOD(r, c, F, D); dijkstra(pair<int,int>(r,c)); DIST[r][c] = cost; } vector<int>order = solve(); vector<pair<int,int>>path; path.push_back(make_pair(0, N)); for (int i = 0; i < N; i++) { if (order[i])path.push_back(make_pair(order[i],i)); } sort(path.begin(), path.end()); foods.push_back(FOOD(sr,sc,0,0)); string ans=""; for (int i = path.size() - 2; i >= 0; i--) { int p1 = path[i].second; int p2 = path[i + 1].second; int r = foods[p1].r; int c = foods[p1].c; int r2 = foods[p2].r; int c2 = foods[p2].c; ans += pathfind(r, c, r2, c2); } reverse(ans.begin(),ans.end()); ans += string(K - ans.size(),'-'); cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Food Collector |
User | kurenai3110 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 6679 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘std::vector<int> solve()’: ./Main.cpp:163:65: error: invalid initialization of non-const reference of type ‘std::vector<int>&’ from an rvalue of type ‘std::vector<int>’ stats[0].push(STATE(0, -1, make_pair(sr, sc), vector<int>(N), 0)); ^ ./Main.cpp:138:2: note: initializing argument 4 of ‘STATE::STATE(int, int, std::pair<int, int>, std::vector<int>&, int)’ STATE(int score_, int time_, pair<int, int>pos_, vector<int>&order_, int loss_) { ^ ./Main.cpp:212:105: error: invalid initialization of non-const reference of type ‘std::vector<int>&’ from an rvalue of type ‘std::vector<int>’ stats[turn + 1].push(STATE(nowState.score + score, time, pair<int, int>(food.r, food.c), next_order(nowState.order, j, turn + 1), loss)); ^ ./Main.cpp:138:2: note: initializing argument 4 of ‘STATE::STATE(int, int, std::pair...