[討論] UVA 11367 Full tank 一直TLE
看板C_and_CPP作者darrenlee1 (darrenleeleelee)時間4年前 (2020/04/28 23:58)推噓0(0推 0噓 1→)留言1則, 1人參與討論串1/2 (看更多)
目前測資看起來是都沒有問題(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://www.ptt.cc/bbs/C_and_CPP/M.1588089488.A.85E.html
→
04/29 01:52,
4年前
, 1F
04/29 01:52, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：