题目传送门
题意:n个人发糖果,B 比 A 多 C的糖果,问最后第n个人比第一个人多多少的糖果
分析:最短路,Dijkstra 优先队列优化可过,SPFA竟然要用栈,队列超时!
代码:
/************************************************
* Author :Running_Time
* Created Time :2015-9-1 19:18:52
* File Name :POJ_3159.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 3e4 + 10;
const int E = 150000 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct Edge {
int v, w, nex;
Edge (int _v = 0, int _w = 0) : v (_v), w (_w) {}
bool operator < (const Edge &r) const {
return w > r.w;
}
}edge[E];
int d[N];
int head[N];
int vis[N];
int cnt[N];
int n, m, e;
void init(void) {
memset (head, -1, sizeof (head));
e = 0;
}
void Dijkstra(int s) {
memset (vis, false, sizeof (vis));
for (int i=1; i<=n; ++i) d[i] = INF;
d[s] = 0;
priority_queue<Edge> Q; Q.push (Edge (s, 0));
while (!Q.empty ()) {
int u = Q.top ().v; Q.pop ();
if (vis[u]) continue;
vis[u] = true;
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v, w = edge[i].w;
if (!vis[v] && d[v] > d[u] + w) {
d[v] = d[u] + w; Q.push (Edge (v, d[v]));
}
}
}
}
void SPFA(int s) {
memset (vis, false, sizeof (vis));
memset (d, INF, sizeof (d));
d[s] = 0; vis[s] = true;
stack<int> S; S.push (s);
while (!S.empty ()) {
int u = S.top (); S.pop ();
vis[u] = false;
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v, w = edge[i].w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (!vis[v]) {
vis[v] = true; S.push (v);
}
}
}
}
}
void add_edge(int u, int v, int w) {
edge[e].v = v, edge[e].w = w;
edge[e].nex = head[u]; head[u] = e++;
}
int main(void) {
while (scanf ("%d%d", &n, &m) == 2) {
init ();
for (int u, v, w, i=1; i<=m; ++i) {
scanf ("%d%d%d", &u, &v, &w);
add_edge (u, v, w);
}
//Dijkstra (1);
SPFA (1);
printf ("%d\n", d[n]);
}
return 0;
}