第一道差分约束
题意：熊孩纸系列…………
A认为B不会比他多c颗糖及
candies[B] <= candies[A] + C
与d[v] <= d[u] + e.cost 类似
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdio>
using namespace std;
#define INF 1<<30
#define MAX_V 50000
#define MAX_E 300000
struct edge
{
int v;
int cost;
int next;
};
struct edge es[MAX_E];
int head[MAX_V];
int len = 0;
void add ( int from, int to, int val )
{
es[len].v = to;
es[len].cost = val;
es[len].next = head[from];
head[from] = len++;
}
int V;
bool inqueue[MAX_V];
int d[MAX_V];
void spfa ( int s )
{
for ( int i = 0; i <= V; i++ )
{ d[i] = INF; }
memset ( inqueue, 0, sizeof inqueue );
d[s] = 0;
inqueue[s] = true;
stack<int> Q;
Q.push ( s );
while ( !Q.empty() )
{
int u = Q.top();
Q.pop();
inqueue[u] = false;
for ( int i = head[u]; i != -1; i = es[i].next )
{
int v = es[i].v;
if ( d[v] > d[u] + es[i].cost )
{
d[v] = d[u] + es[i].cost;
if ( !inqueue[v] )
{
Q.push ( v );
inqueue[v] = true;
}
}
}
}
}
void init()
{
int M;
scanf ( "%d%d", &V, &M );
memset ( head, -1, sizeof head );
for ( int i = 0; i < M; i++ )
{
int from, to, val;
scanf ( "%d%d%d", &from, &to, &val );
add ( from, to, val );
}
}
int main()
{
init();
spfa ( 1 );
printf ( "%d\n", d[V] );
return 0;
}
