最短路 西北大学2019年春季校赛 （ 重现赛 ) 房间迷宫

迷宫"/>

最短路 西北大学2019年春季校赛 （ 重现赛 ) 房间迷宫

题目：=1461（密码：jwjtxdy）

学习一下 求一个数的约束 复杂度n*logn

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iostream>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
struct heapnode
{int u;ll d;heapnode(int u=0,ll d=0):u(u),d(d){}bool operator<(const heapnode&a)const{return a.d < d;}
};
vector<int>G[maxn];
vector<int>num[maxn];
ll dis[maxn];
bool vis[maxn];
int a[maxn], b[maxn], c[maxn], n;void dij(int s)
{for (int i = 0; i <= n; i++) dis[i] = inf;dis[s] = 0;memset(vis, 0, sizeof(vis));priority_queue<heapnode>que;que.push(heapnode(s, 0));while(!que.empty()){heapnode x = que.top(); que.pop();int u = x.u;if (vis[u]) continue;vis[u] = 1;for(int i=0;i<G[u].size();i++){int now = G[u][i];if(dis[now]>dis[u]+a[now]){dis[now] = dis[u] + a[now];//printf("www  dis[%d]=%lld dis[%d]=%lld\n", now, dis[now],u,dis[u]);
                que.push(heapnode(now, dis[now]));}}//printf("c[%d]=%d\n",u, c[u]);int len = num[c[u]].size();// printf("%d\n", len);for(int i=0;i<len&&num[c[u]][i]+u<=n;i++){int y = num[c[u]][i] + u;// printf("y=%d\n", y);// printf("a[%d]=%d\n", y, a[y]);if(dis[y]>dis[u]+b[u]+a[y]){dis[y] = dis[u] + b[u] + a[y];// printf("b[%d]=%d a[%d]=%d\n", u, b[u], y, a[y]);// printf("dis[%d]=%lld dis[%d]=%lld\n", y, dis[y],u,dis[u]);
                que.push(heapnode(y, dis[y]));}}}
}int main()
{for (int i = 1; i < maxn; ++i) {for (int j = i; j < maxn; j += i) {num[j].push_back(i);//先把每个数的因子有哪些打个表，由调和级数可知复杂度为o(nlog n)
        }}int v;scanf("%d", &n);for(int i=1;i<=n;i++){scanf("%d%d%d%d", &a[i], &b[i], &c[i], &v);G[i].push_back(v);}dij(1);if (dis[n] >= inf) printf("-1\n");else printf("%lld\n", dis[n]+a[1]);return 0;
}

转载于:.html