HDU 4725 The Shortest Path in Nya Graph——建图+dijkstra

HDU 4725 The Shortest Path in Nya Graph——建图+dijkstra

这道题难在建图

首先一个layer下可能有多个节点，如果两个layer下各有50000个节点，那么就要建25亿条边，显然是不现实的，正确做法是把层次看做节点，将层次节点和普通节点按照一定的规则进行连接

然后不相邻的layer不能建边，也就是说注意判重

最后注意层次节点和普通节点的连接规则，一开始我是这样想的：

假设x层次节点下面有1 2 3，y层次节点下有4 5 6，那么我就在1 2 3与x间建立权值为0的无向边，在x与y之间建立权值为c的无向边，在y与4 5 6之间建立权值为0的无向边，后来发现有个致命的错误：

对于上面的例子。因为边是无向的，所以1可以回到2！而且权值为0！如果1到2本来权值为10000，那么现在就成了0，很明显是错误的，所以我换了种建边方法：

在1 2 3与y之间建立有向边（权值为0），1 2 3指向y，在y与4 5 6之间建立有向边（权值为c），让y指向4 5  6，同理在4 5 6与x之间建立有向边，在x与1 2 3之间建立有向边

然后dijkstra就可以了，改了挺多次，代码改得挺乱。。。。。。

#include #include #include #include #include #include using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int maxn = 1e5 + 10;bool vis[maxn * 2];int T, N, M, C, tot, head[maxn * 2], date[maxn * 2];ll dis[maxn * 2];struct Edge { int to, val, next;}edge[maxn * 10];struct Node { int u; ll dis; Node(int x, ll y) : u(x), dis(y) {} bool operator < (const Node &node) const { return dis > node.dis; }};vector layer[maxn * 2];void init() { tot = 0; for (int i = 1; i <= N * 2; i++) head[i] = -1, layer[i].clear();}void addedge(int u, int v, int val) { tot++; edge[tot].to = v; edge[tot].val = val; edge[tot].next = head[u]; head[u] = tot;}ll dijkstra(int s) { for (int i = 1; i <= N * 2; i++) dis[i] = INF, vis[i] = false; dis[s] = 0; priority_queue q; q.push(Node(s, 0)); while (!q.empty()) { Node node = q.top(); q.pop(); int u = node.u; if (vis[u]) continue; vis[u] =true; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, val = edge[i].val; if (dis[v] > dis[u] + val) { dis[v] = dis[u] + val; q.push(Node(v, dis[v])); } } } return dis[N] == INF ? -1 : dis[N];}int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d %d %d", &N, &M, &C); init(); int temp, cnt = 0; memset(vis, false, sizeof(vis)); for (int i = 1; i <= N; i++) { scanf("%d", &temp); layer[temp + N].push_back(i); if (!vis[temp + N]) vis[temp + N] = true, date[++cnt] = temp + N; } sort(date + 1, date + 1 + cnt); for (int i = 2; i <= cnt; i++) { int u = date[i - 1], v = date[i]; if (u + 1 != v) continue; for (int j = 0; j < layer[v].size(); j++) { addedge(v, layer[v][j], C); addedge(layer[v][j], u, 0); } for (int j = 0; j < layer[u].size(); j++) { addedge(u, layer[u][j], C); addedge(layer[u][j], v, 0); } } for (int i = 1; i <= M; i++) { int u, v, val; scanf("%d %d %d", &u, &v, &val); addedge(u, v, val); addedge(v, u, val); } if (N == 0) { printf("Case #%d: -1\n", kase); continue; } printf("Case #%d: ", kase); cout << dijkstra(1) << endl; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。