不能用全局数组d[u]>d[rhs.u]。
这样后面会修改d[u]值然而本来里面的点顺序不该修改,却被修改了。
应该用栈还存进去的临时变量,比如d>rhs.d。
优先队列重载小于号'<'
struct Node {
int u,d,c;
bool operator<(const Node &rhs)const {
if(d!=rhs.d)
return d > rhs.d;
return c > rhs.c;
}
Node(int u_,int d_,int c_):u(u_),d(d_),c(c_){}
};
两种加边法:
struct Edge {
int u, v, d, c;
Edge(int u_,int v_,int d_,int c_):u(u_),v(v_),d(d_),c(c_){}
Edge(){}
};
Edge edge[100005*2];
void add(int u, int v, int d, int c) {
g[u].push_back(id);
g[v].push_back(id + 1);
id += 2;
edge[id-2]=Edge(u, v, d, c);
edge[id-1]=Edge(v, u, d, c);
}
struct Edge {
int u, v, d, c, next;
Edge(int u_,int v_,int d_,int c_,int next_):u(u_),v(v_),d(d_),c(c_),next(next_){}
Edge(){}
};
Edge edge[100005*2];
void add(int u, int v, int d, int c) {
edge[id] = Edge(u, v, d, c, head[u]);head[u] = id++;
edge[id] = Edge(v, u, d, c, head[v]);head[v] = id++;
}