dij 70pts代码

#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, int> PII;

const int N = 80010, M = 400010;

int n, m, st;
int h[N], hs[N], e[M], ne[M], w[M], k[M], idx;
int dfn[N], low[N], id[N], s[N], timestamp, scc_cnt;
int dist[N];
priority_queue<PII, vector<PII> > q;
bool in_stk[N], b[N];
stack<int> stk;

void add(int h[], int a, int b, int c, int d)
{
	e[idx] = b, ne[idx] = h[a], w[idx] = c, k[idx] = d, h[a] = idx ++;
	return;
}

void dijkstra(int st)
{
	for (int i = 0; i <= n; i ++ ) dist[i] = INT_MIN, b[i] = 0;
	dist[st] = s[st]; q.push({dist[st], st});
	
	while (!q.empty())
	{
		PII t = q.top();
		q.pop();
		
		if(b[t.second]) continue;
		b[t.second] = 1;
		
		for (int i = hs[t.second]; ~i; i = ne[i])
		{
			int j = e[i];
			if(dist[j] < dist[t.second] + w[i] + s[j])
			{
				dist[j] = dist[t.second] + w[i] + s[j];
				q.push({dist[j], j});
			}
		}
	}
	return;
}

void tarjan(int u)
{
	dfn[u] = low[u] = ++ timestamp;
	stk.push(u); in_stk[u] = 1;
	
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if(!dfn[j])
		{
			tarjan(j);
			low[u] = min(low[u], low[j]);
		}
		else if(in_stk[j]) low[u] = min(low[u], low[j]);
	}
	if(dfn[u] == low[u])
	{
		++ scc_cnt;
		int y;
		do
		{
			y = stk.top();
			id[y] = scc_cnt;
			in_stk[y] = 0;
			stk.pop();
		} while (y != u);
	}
	return;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; i ++ ) h[i] = -1, hs[i] = -1;
	for (int i = 1; i <= m; i ++ )
	{
		int a, b, c;
		long double d;
		scanf("%d%d%d%llf", &a, &b, &c, &d);
		add(h, a, b, c, d * 10);
	}
	
	for (int i= 1; i <= n; i ++ )
		if(!dfn[i]) tarjan(i);
	
	for (int i = 1; i <= n; i ++ )
	{
		for (int t = h[i]; ~t; t = ne[t])
		{
			int j = e[t], c = w[t], d = k[t];
			if(id[i] == id[j])
			{
				while (c > 0)
				{
					s[id[i]] += c;
					c = c * d / 10;
				}
			}
			else { add(hs, id[i], id[j], c, d); }
		}
	}
	
	scanf("%d", &st);
	dijkstra(id[st]);
	
	int res = 0;
	for (int i = 1; i <= scc_cnt; i ++ )
	{
		res = max(res, dist[i]);
	}
	
	printf("%d\n", res);
	
	return 0;
}

spfa 过了的代码

#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 80010, M = 400010;

int n, m, st;
int h[N], hs[N], e[M], ne[M], w[M], k[M], idx;
int dfn[N], low[N], id[N], s[N], timestamp, scc_cnt;
int dist[N];
queue<int> q;
bool in_stk[N], b[N];
stack<int> stk;

void add(int h[], int a, int b, int c, int d)
{
	e[idx] = b, ne[idx] = h[a], w[idx] = c, k[idx] = d, h[a] = idx ++;
	return;
}

void spfa(int st)
{
	for (int i = 0; i <= n; i ++ ) dist[i] = -0x3f3f3f3f, b[i] = 0;
	dist[st] = s[st]; q.push(st);
	
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		
		b[t] = 0;
		
		for (int i = hs[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(dist[j] < dist[t] + w[i] + s[j])
			{
				dist[j] = dist[t] + w[i] + s[j];
				if(!b[j])
				{
					q.push(j);
					b[j] = 1;
				}
			}
		}
	}
	return;
}

void tarjan(int u)
{
	dfn[u] = low[u] = ++ timestamp;
	stk.push(u); in_stk[u] = 1;
	
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if(!dfn[j])
		{
			tarjan(j);
			low[u] = min(low[u], low[j]);
		}
		else if(in_stk[j]) low[u] = min(low[u], low[j]);
	}
	if(dfn[u] == low[u])
	{
		++ scc_cnt;
		int y;
		do
		{
			y = stk.top();
			id[y] = scc_cnt;
			in_stk[y] = 0;
			stk.pop();
		} while (y != u);
	}
	return;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; i ++ ) h[i] = -1, hs[i] = -1;
	for (int i = 1; i <= m; i ++ )
	{
		int a, b, c;
		double d;
		scanf("%d%d%d%lf", &a, &b, &c, &d);
		add(h, a, b, c, d * 10);
	}
	
	for (int i= 1; i <= n; i ++ )
		if(!dfn[i]) tarjan(i);
	
	for (int i = 1; i <= n; i ++ )
	{
		for (int t = h[i]; ~t; t = ne[t])
		{
			int j = e[t], c = w[t], d = k[t];
			if(id[i] == id[j])
			{
				while (c > 0)
				{
					s[id[i]] += c;
					c = c * d / 10;
				}
			}
			else { add(hs, id[i], id[j], c, d); }
		}
	}
	
	scanf("%d", &st);
	spfa(id[st]);
	
	int res = 0;
	for (int i = 1; i <= scc_cnt; i ++ )
	{
		res = max(res, dist[i]);
	}
	
	printf("%d\n", res);
	
	return 0;
}