実現したいこと
与えられた始点と終点に対して k(1≦k≦5)番目まで短い経路の距離を求める.
※ある地点を2度以上通るような無駄な回り道を含む経路はk番目の最短路とはみなさない.
発生している問題・分からないこと
k番目の最短路の計算方法が分からない
該当のソースコード
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #define MAXN 1100 #define MAXM 500 #define MAXQ 100 #define INF 1e18 #define EPS 1e-8 #define MAXK 5 typedef struct { double x, y; } Point; typedef struct { int a, b; } Segment; typedef struct Edge { int to; double cost; struct Edge* next; } Edge; Point points[MAXN]; Segment segs[MAXM]; Edge* graph[MAXN]; int node_count = 0; int equal(Point p1, Point p2) { return fabs(p1.x - p2.x) < EPS && fabs(p1.y - p2.y) < EPS; } double distance(Point p1, Point p2) { double dx = p1.x - p2.x, dy = p1.y - p2.y; return sqrt(dx * dx + dy * dy); } int intersect(Point p1, Point q1, Point p2, Point q2, double* ix, double* iy) { double a = q1.x - p1.x; double b = -(q2.x - p2.x); double c = q1.y - p1.y; double d = -(q2.y - p2.y); double e = p2.x - p1.x; double f = p2.y - p1.y; double det = a * d - b * c; if (fabs(det) < EPS) return 0; double s = (d * e - b * f) / det; double t = (-c * e + a * f) / det; if (s < EPS || s > 1 - EPS || t < EPS || t > 1 - EPS) return 0; *ix = p1.x + s * (q1.x - p1.x); *iy = p1.y + s * (q1.y - p1.y); if (equal((Point){*ix, *iy}, p1) || equal((Point){*ix, *iy}, q1) || equal((Point){*ix, *iy}, p2) || equal((Point){*ix, *iy}, q2)) return 0; return 1; } void add_edge(int u, int v, double cost) { Edge* e = malloc(sizeof(Edge)); e->to = v; e->cost = cost; e->next = graph[u]; graph[u] = e; } int cmp_point(const void* a, const void* b) { Point* p = (Point*)a; Point* q = (Point*)b; if (fabs(p->x - q->x) > EPS) return p->x < q->x ? -1 : 1; if (fabs(p->y - q->y) > EPS) return p->y < q->y ? -1 : 1; return 0; } int get_node_index(Point p) { for (int i = 0; i < node_count; i++) { if (equal(points[i], p)) return i; } points[node_count++] = p; return node_count - 1; } void build_graph(int M) { for (int i = 0; i < M; i++) { Point p1 = points[segs[i].a]; Point p2 = points[segs[i].b]; Point seg_pts[MAXN]; int count = 0; seg_pts[count++] = p1; seg_pts[count++] = p2; for (int j = 0; j < M; j++) { if (i == j) continue; double ix, iy; if (intersect(p1, p2, points[segs[j].a], points[segs[j].b], &ix, &iy)) { seg_pts[count++] = (Point){ix, iy}; } } qsort(seg_pts, count, sizeof(Point), cmp_point); for (int k = 0; k < count - 1; k++) { int u = get_node_index(seg_pts[k]); int v = get_node_index(seg_pts[k + 1]); double d = distance(seg_pts[k], seg_pts[k + 1]); add_edge(u, v, d); add_edge(v, u, d); } } } int parse_node(char* s, int N) { if (s[0] == 'C') { int id = atoi(s + 1); if (id < 1 || id > node_count - N) return -1; return N + id - 1; } else { int id = atoi(s); if (id < 1 || id > N) return -1; return id - 1; } } void reconstruct_path(int start, int goal, int prev[], int N) { int path[MAXN], len = 0; for (int v = goal; v != -1; v = prev[v]) { path[len++] = v; } for (int i = len - 1; i >= 0; i--) { if (path[i] < N) printf("%d", path[i] + 1); else printf("C%d", path[i] - N + 1); if (i > 0) printf(" "); } printf("\n"); } void dijkstra(int start, double dist[], int prev[]) { int used[MAXN] = {0}; for (int i = 0; i < MAXN; i++) { dist[i] = INF; prev[i] = -1; } dist[start] = 0; for (int i = 0; i < node_count; i++) { int v = -1; for (int j = 0; j < node_count; j++) { if (!used[j] && (v == -1 || dist[j] < dist[v])) v = j; } if (v == -1 || dist[v] == INF) break; used[v] = 1; for (Edge* e = graph[v]; e; e = e->next) { if (dist[e->to] > dist[v] + e->cost) { dist[e->to] = dist[v] + e->cost; prev[e->to] = v; } else if (fabs(dist[e->to] - (dist[v] + e->cost)) < EPS) { if (v < prev[e->to]) prev[e->to] = v; } } } } void yen_k_shortest_paths(int start, int goal, int k, double dist[], int prev[]) { double dist_all[MAXK][MAXN]; int prev_all[MAXK][MAXN]; dijkstra(start, dist, prev); memcpy(dist_all[0], dist, sizeof(double) * MAXN); memcpy(prev_all[0], prev, sizeof(int) * MAXN); for (int i = 1; i < k; i++) { double d[MAXN]; int p[MAXN]; memcpy(d, dist_all[i - 1], sizeof(double) * MAXN); memcpy(p, prev_all[i - 1], sizeof(int) * MAXN); } } int main() { int N, M, P, Q; scanf("%d %d %d %d", &N, &M, &P, &Q); for (int i = 0; i < N; i++) { scanf("%lf %lf", &points[i].x, &points[i].y); } node_count = N; for (int i = 0; i < M; i++) { scanf("%d %d", &segs[i].a, &segs[i].b); segs[i].a--; segs[i].b--; } build_graph(M); for (int q = 0; q < Q; q++) { char s1[10], s2[10]; int k; scanf("%s %s %d", s1, s2, &k); int start = parse_node(s1, N); int goal = parse_node(s2, N); if (start == -1 || goal == -1) { printf("NA\n"); continue; } double dist[MAXN]; int prev[MAXN]; yen_k_shortest_paths(start, goal, k, dist, prev); } return 0; }
試したこと・調べたこと
- teratailやGoogle等で検索した
- ソースコードを自分なりに変更した
- 知人に聞いた
- その他
上記の詳細・結果
セグメンテーションフォールトになってしまった
補足
制約
2≦N≦200, 1≦M<N, 0≦x,y≦104, P=0, 0≦Q≦100.
出力
各始点と終点のペアに対して、k番目まで短い経路の距離を出力する. 存在しない地点に対する問い合わせが来た場合や、到達できない場合はNAと出力する. 最短経路が存在する場合、2番目、3番目、…、k番目に短い経路が存在しなければ、存在しない分は出力しない.
入出力例
入力例
6 5 0 2
0 0
2 5
4 7
5 5
7 1
9 5
1 4
1 6
2 5
3 5
4 6
1 4 5
C1 C3 10
出力例
7.07107
8.65895
8.99493
9.81418
12.7711
2.68432
3.83003
6.79648
9.46671
11.9
16.0121
