HDU 2851dp 및 dijkstra
#include <bits/stdc++.h>
using namespace std;
const int MAX_V = 2005;
const int INF = 0x3f3f3f3f;
struct rode
{
int start, end, danger;
};
int n, m;
int *dp;
rode *p;
void solve()
{
dp[0] = p[0].danger;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (p[j].end >= p[i].start)
dp[i] = min(dp[i], dp[j] + p[i].danger);
}
}
}
int main(int argc, char const *argv[])
{
int kase;
cin >> kase;
while (kase--)
{
cin >> n >> m;
p = new rode[n];
dp = new int[n];
for (int i = 0; i < n; i++)
cin >> p[i].start >> p[i].end >> p[i].danger;
fill(dp, dp + n, INF);
solve();
while (m--)
{
int inp;
cin >> inp;
cout << (dp[inp - 1] == INF ? -1 : dp[inp - 1]) << endl;
}
delete[] p, dp;
}
return 0;
}
dp 알고리즘:dp[i] = min(dp[i], dp[j] + p[i].danger);
4
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int to, cost;
bool operator>(edge &p)
{
return cost > p.cost;
}
edge(int a, int b): to(a), cost(b) {}
};
const int MAX_V = 2001;
typedef pair<int, int>P;
int v;
std::vector<edge> G[MAX_V];
int d[MAX_V];
const int INF = 0x3f3f3f3f;
void dijkstra(int s)
{
priority_queue<P, vector<P> >que;
fill(d, d + v, INF);
d[s] = 0;
que.push(P(0, s));
while (!que.empty())
{
P p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first)
continue;
for (int i = 0; i < G[v].size(); i++)
{
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost)
{
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}
struct rode
{
int start, end, danger;
};
int main(int argc, char const *argv[])
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int kase;
cin >> kase;
while (kase--)
{
int n, m;
cin >> n >> m;
v = n;
memset(d, 0, sizeof(d));
for (int i = 0; i < n; i++)
G[i].clear();
rode pro[MAX_V];
for (int i = 0; i < n; ++i)
cin >> pro[i].start >> pro[i].end >> pro[i].danger;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (pro[j].end >= pro[i].start)
{
G[j].push_back(edge(i, pro[i].danger));
//cout << i << " " << j << " " << pro[i].danger << endl;
}
}
}
dijkstra(0);
for (int i = 0; i < m; i++)
{
int t;
cin >> t;
cout << ((d[t - 1] == INF) ? -1 : d[t - 1] + pro[0].danger) << endl;
}
}
return 0;
}
dijkstra 알고리즘: 시간 초과 이유
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.