4
dist[v] = dist[u] + c;
for (j=0; j<n; j++)
// 下面的加法可能导致溢出,INF不能取太大
if (vis[j]==0 &&
lowcost[pre]+cost[pre][j]<lowcost[j]){
lowcost[j] = lowcost[pre] + cost[pre][j];
path[j] = pre;
}
for (j=0; j<n; j++)
if (vis[j] == 0 && lowcost[j] < min){
min = lowcost[j]; pre = j;
}
vis[pre] = 1;
}
}
/*==================================================*\
| Dijkstra O(E * log E)
| INIT: 调用init(nv, ne)读入边并初始化;
| CALL: dijkstra(n, src); dist[i]为src到i的最短距离
\*==================================================*/
#define typec int // type of cost
const typec inf = 0x3f3f3f3f; // max of cost
typec cost[E], dist[V];
int e, pnt[E], nxt[E], head[V], prev[V], vis[V];
struct qnode {
int v; typec c;
qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {}
bool operator < (const qnode& r) const { return c>r.c; }
};
void dijkstra(int n, const int src){
qnode mv;
int i, j, k, pre;
priority_queue<qnode> que;
vis[src] = 1; dist[src] = 0;
que.push(qnode(src, 0));
for (pre = src, i=1; i<n; i++) {
for (j = head[pre]; j != -1; j = nxt[j]) {
k = pnt[j];
if (vis[k] == 0 &&
dist[pre] + cost[j] < dist[k]){
dist[k] = dist[pre] + cost[j];
que.push(qnode(pnt[j], dist[k]));
prev[k] = pre;
}
}
while (!que.empty() && vis[que.top().v] == 1)
que.pop();
if (que.empty()) break;
mv = que.top(); que.pop();
vis[pre = mv.v] = 1;
}
}
inline void addedge(int u, int v, typec c){
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
}
void init(int nv, int ne){
int i, u, v; typec c;
e = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(prev, -1, sizeof(prev));
for (i = 0; i < nv; i++) dist[i] = inf;
for (i = 0; i < ne; ++i) {
scanf("%d%d%d", &u, &v, &c);// %d: type of cost
addedge(u, v, c); // vertex: 0 ~ n-1, 单向边
}
}
/*==================================================*\
| BellmanFord 单源最短路 O(VE)
| 能在一般情况下，包括存在负权边的情况下，解决单源最短路径问题
| INIT: edge[E][3]为边表
| CALL: bellman(src);有负环返回0;dist[i]为src到i的最短距
| 可以解决差分约束系统: 需要首先构造约束图，构造不等式时>=表示求最
小值, 作为最长路，<=表示求最大值, 作为最短路 （v-u <= c:a[u][v] =
c）
\*==================================================*/
#define typec int // type of cost
const typec inf=0x3f3f3f3f; // max of cost
int n, m, pre[V], edge[E][3];
typec dist[V];
int relax (int u, int v, typec c){
if (dist[v] > dist[u] + c) {
pre[v] = u; return 1;
}
return 0;
}
int bellman (int src){
int i, j;
for (i=0; i<n; ++i) {
dist[i] = inf; pre[i] = -1;
}
dist[src] = 0; bool flag;
for (i=1; i<n; ++i){
flag = false; // 优化
for (j=0; j<m; ++j) {
if( 1 == relax(edge[j][0], edge[j][1],
edge[j][2]) ) flag = true;
}
if( !flag ) break; }
for (j=0; j<m; ++j) {
if (1 == relax(edge[j][0], edge[j][1], edge[j][2]))
return 0; // 有负圈
}
return 1;
}
/*==================================================*\
| SPFA(Shortest Path Faster Algorithm)
Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 它可以在
O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
原理：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻
接点的距离估计值的改变。
判断负权回路：记录每个结点进队次数，超过|V|次表示有负权。
\*==================================================*/
// POJ 3159 Candies
const int INF = 0x3F3F3F3F;
const int V = 30001;
const int E = 150001;
int pnt[E], cost[E], nxt[E];
int e, head[V]; int dist[V]; bool vis[V];
int main(void){
int n, m;
while( scanf("%d%d", &n, &m) != EOF ){
int i, a, b, c;
e = 0;
memset(head, -1, sizeof(head));
for( i=0; i < m; ++i )
{// b-a <= c, 有向边(a, b):c ，边的方向！！！
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
printf("%d\n", SPFA(1, n));
}
return 0;
}
int relax(int u, int v, int c){
if( dist[v] > dist[u] + c ) {
dist[v] = dist[u] + c; return 1;
}
return 0;
}
inline void addedge(int u, int v, int c){
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
}
int SPFA(int src, int n)
{ // 此处用堆栈实现，有些时候比队列要快
int i;
for( i=1; i <= n; ++i ){ // 顶点1...n
vis[i] = 0; dist[i] = INF;
}
dist[src] = 0;
int Q[E], top = 1;
Q[0] = src; vis[src] = true;
while( top ){
int u, v;
u = Q[--top]; vis[u] = false;
for( i=head[u]; i != -1; i=nxt[i] ){
v = pnt[i];
if( 1 == relax(u, v, cost[i]) && !vis[v] ) {
Q[top++] = v; vis[v] = true;
}
}
}
return dist[n];
}
评论0