NOIP2017 D1T3 공원 구경
5160 단어 NOIP 문제 해결 보고서기억화 검색최단로
제목 배경:
NOIP2017 D1T3
분석: 기억화 검색 + 최단로
카드 상수라니... 시험장에서 spfa의 이동이 나오지 않았기 때문에 이 문제는 30pts에 불과하다·········· 내려와서야 알 수 있듯이 이것은 매우 명백한 DP를 검색하는 것이 아니냐··············· 정말 자신의 시험장에서 무엇을 생각하는지 모른다········· 정의 상태 dp[i][j]는 i에 이르기까지 최단거리 차치가 j인 방안수는 먼저 dijkstra로 최단거리를 한 번 뛰고 나서 역변을 만들고 기억화 검색을 한 번 뛰면 된다고 한다.그 다음에 0환을 어떻게 판정하고 0환의 성질을 고려하면 분명히 0환이 존재한다는 것은 당신이 어떤 상태를 검색하고 처리할 때 자신으로 돌아간다는 것을 의미한다. 그러면 우리는 시스템 창고에 현재 있는 상태를 표시하기만 하면 된다. 만약에 현재 자신의 상태가 시스템 창고에 있다는 것을 발견하면 0환이 존재하고 출력-1이 존재하면 된다. 그리고 검색하는 경계 문제도 있다. 만약에 i=1, j=0을 사용하면1을 되돌리는 것은 옳지 않다. 1 자체가 0환에 있으면 RE가 떨어지기 때문에 1에서 0으로 한 변을 연결하고 i=0, j=0에 1을 되돌리면 된다.
Source:
/*
created by scarlyw
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
inline char read() {
static const int IN_LEN = 1024 * 1024;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
///*
template
inline void R(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return ;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = read())
x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}
//*/
const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
template
inline void W(T x) {
static int buf[30], cnt;
if (x == 0) write_char('0');
else {
if (x < 0) write_char('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) write_char(buf[cnt--]);
}
}
inline void flush() {
fwrite(obuf, 1, oh - obuf, stdout);
}
/*
template
inline void R(T &x) {
static char c;
static bool iosig;
for (c = getchar(), iosig = false; !isdigit(c); c = getchar())
if (c == '-') iosig = true;
for (x = 0; isdigit(c); c = getchar())
x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}
//*/
const int MAXN = 100000 + 10;
const int MAXK = 50 + 5;
int n, m, x, y, k, t, mod;
inline void add(int &x, int t) {
x += t, (x >= mod) ? (x -= mod) : 0;
}
struct node {
int to, w;
node(int to = 0, int w = 0) : to(to), w(w) {}
inline bool operator < (const node &a) const {
return w > a.w;
}
} ;
struct edges {
int x, y, z;
} e[MAXN << 1];
std::vector edge[MAXN];
inline void add_edge(int x, int y, int z) {
edge[x].push_back(node(y, z));
}
inline void read_in() {
R(n), R(m), R(k), R(mod);
for (int i = 1; i <= n; ++i) edge[i].clear();
for (int i = 1; i <= m; ++i)
R(e[i].x), R(e[i].y), R(e[i].z), add_edge(e[i].x, e[i].y, e[i].z);
}
int dis[MAXN];
inline void dijkstra(int s) {
static bool vis[MAXN];
memset(dis, 127, sizeof(int) * (n + 5));
memset(vis, false, sizeof(bool) * (n + 5));
std::priority_queue q;
q.push(node(s, 0)), dis[s] = 0;
while (!q.empty()) {
while (!q.empty() && vis[q.top().to]) q.pop();
if (q.empty()) break ;
int cur = q.top().to;
q.pop(), vis[cur] = true;
for (int p = 0; p < edge[cur].size(); ++p) {
node *e = &edge[cur][p];
if (!vis[e->to] && dis[e->to] > dis[cur] + e->w)
dis[e->to] = dis[cur] + e->w, q.push(node(e->to, dis[e->to]));
}
}
}
int f[MAXN][MAXK];
bool vis[MAXN][MAXK];
inline void clear() {
for (int i = 1; i <= n; ++i) edge[i].clear();
for (int i = 1; i <= m; ++i) add_edge(e[i].y, e[i].x, e[i].z);
add_edge(1, 0, 0), memset(f, -1, sizeof(f)), memset(vis, 0, sizeof(vis));
dis[0] = 0;
}
int dfs(int cur, int cur_dis) {
int d = cur_dis - dis[cur];
if (d < 0) return 0;
if (~f[cur][d]) return f[cur][d];
if (cur == 0 && cur_dis == 0) return 1;
if (vis[cur][d]) return -1;
vis[cur][d] = true;
int ret = 0;
for (int p = 0; p < edge[cur].size(); ++p) {
node *e = &edge[cur][p];
int res = dfs(e->to, cur_dis - e->w);
if (~res) add(ret, res);
else return -1;
}
return vis[cur][d] = false, f[cur][d] = ret;
}
inline void solve() {
read_in(), dijkstra(1), clear();
int ans = 0;
for (int i = 0; i <= k; ++i) {
int res = dfs(n, dis[n] + i);
if (~res) add(ans, res);
else {
std::cout << "-1
";
return ;
}
}
std::cout << ans << '
';
}
int main() {
R(t);
while (t--) solve();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode10+leetcode44 정규 일치 문제 요약이 두 문제는 사실 모두 일치 유형에 속하는 문제이다. 모두'*'는 여러 문자를 임의로 일치할 수 있다는 것을 표시하고 하나는'있다. '단일 문자와 일치할 수 있음을 나타냅니다. 비교적 생각하는 귀속 사고방식: 귀속...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.