作者darrenlee1 (darrenleeleelee)
看板C_and_CPP
标题[讨论] UVA 11367 Full tank 一直TLE
时间Tue Apr 28 23:58:04 2020
目前测资看起来是都没有问题(udebug也过)，把cin都改成scanf，不知道还有哪边可以优化，一直TLE，想请各位帮忙看一下。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000+10;
int n, m, u, v, d, c, s, e, Q;
int cost[maxn];
int weight[maxn][maxn];
vector<int> adj[maxn];
int dp[maxn][100+10];
struct Car
{
int cur, left, costSum;
bool operator<(const Car &other)const{
return costSum > other.costSum;
}
};
int dij()
{
if(s == e) return 0;
for(int i = 0; i < n; i++)
for(int j = 0; j <= c; j++)
dp[i][j] = 1e9;
priority_queue<Car> pq;
pq.push(Car{s, 0, 0});
while(!pq.empty()){
auto top = pq.top(); pq.pop();
if(dp[top.cur][top.left] < top.costSum) continue;
if(top.cur == e && top.left == 0) return dp[top.cur][top.left];
for(auto i : adj[top.cur]){
if(c < weight[top.cur][i]) continue;
for(int j = top.left; j <= c; j++){
if(j < weight[top.cur][i]) continue;
int OilCost = cost[top.cur] * (j - top.left);
int temp = j - weight[top.cur][i];
if(dp[i][temp] > top.costSum + OilCost){
dp[i][temp] = top.costSum + OilCost;
}
pq.push(Car{i, j - weight[top.cur][i], top.costSum + OilCost});
}
}
}
return 1e9;
}
int main(int argc, char const *argv[])
{
while(scanf("%d%d", &n, &m) != EOF){
for(int i = 0; i < n; i++){
adj[i].clear();
scanf("%d", &cost[i]);
}
for(int i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back(v);
adj[v].push_back(u);
weight[u][v] = d;
weight[v][u] = d;
}
scanf("%d", &Q);
while(Q--){
scanf("%d%d%d", &c, &s, &e);
int res = dij();
if(res == 1e9) printf("impossible\n");
else printf("%d\n", res);
}
}
return 0;
}
题目在这边
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=2352&mosmsg=Submission+received+with+ID+24949480
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.141.67.113 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1588089488.A.85E.html
1F：→ nevak: dfs先把路线走出来再回头算最省钱的加油法会不会比较好呢 04/29 01:52