ACM/ICPC 2010 哈尔滨现场赛 Seaside 题解
这道题是一道水的模板题，就是求个单源最短路。而且一开始我还想多了，还以为有负权环，结果居然没有。所以整道题就水了。SPFA 水过，唯一与模板不同的地方，就是它里面的节点有一个属性，叫做“是否是海滨城市”。求得单源最短路之后，要把所有的海滨城市的结果进行比较，取其中距离最短的那个。
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #include <queue> #include <cstdio> #include <climits> #include <cstring> using namespace std; const int N = 15; const int M = 155; const int inf = INT_MAX >> 1; struct glist { int we[M], fe[N], ne[M], he[M], m, n; bool seaside[N]; inline void reset(int graph_size = 0) { memset(fe, -1, sizeof fe); memset(seaside, false, sizeof seaside); m = 0; n = graph_size; } inline void insert(int u, int v, int weight) { we[m] = weight; ne[m] = fe[u]; he[m] = v; fe[u] = m++; } }; struct spfa { int dist[N]; bool inqu[N]; inline void reset() { for (int i = 0; i < N; ++i) dist[i] = inf; memset(inqu, false, sizeof inqu); } inline void solve(const glist &g, int start) { queue<int> qu; qu.push(start); inqu[start] = true; dist[start] = 0; while (!qu.empty()) { int u = qu.front(); qu.pop(); inqu[u] = false; for (int e = g.fe[u]; e != -1; e = g.ne[e]) { int v = g.he[e]; int d = dist[u] + g.we[e]; if (d < dist[v]) { dist[v] = d; if (!inqu[v]) { qu.push(v); inqu[v] = true; } } } } } }; glist graph; spfa shortest_path; int main() { // freopen("input.txt", "r", stdin); while (scanf("%d", &graph.n) != EOF) { graph.reset(graph.n); for (int i = 0; i < graph.n; ++i) { int m, p; scanf("%d %d", &m, &p); if (p == 0) graph.seaside[i] = false; else graph.seaside[i] = true; for (int j = 0; j < m; ++j) { int s, l; scanf("%d %d", &s, &l); graph.insert(i, s, l); } } shortest_path.reset(); shortest_path.solve(graph, 0); int result = inf; for (int i = 0; i < graph.n; ++i) if (graph.seaside[i] && shortest_path.dist[i] < result) result = shortest_path.dist[i]; printf("%d\n", result); } return 0; } |
