图论–最长路–基于SPFA的调整模板 Posted on 2023年3月22日 by hackdl #include#include#include#include#include#include#include#include#include#include#include#define Swap(a,b) a^=b^=a^=b#define cini(n) scanf("%d",&n)#define cinl(n) scanf("%lld",&n)#define cinc(n) scanf("%c",&n)#define cins(s) scanf("%s",s)#define coui(n) printf("%d",n)#define couc(n) printf("%c",n)#define coul(n) printf("%lld",n)#define speed ios_base::sync_with_stdio(0)#define Max(a,b) a>b?a:b#define Min(a,b) a#define mem(n,x) memset(n,x,sizeof(n))#define INF 0x3f3f3f3f#define maxn 100010#define Ege 100000000#define Vertex 1005#define esp 1e-9#define mp(a,b) make_pair(a,b)using namespace std;typedef long long ll;typedef pair PII;struct Node{ int to, lat, val; //边的右端点，边下一条边，边权};Node edge[1000005];int head[1005],tot,dis[1005],N,M,vis[1005];void add(int from, int to, int dis){ edge[++tot].lat = head[from]; edge[tot].to = to; edge[tot].val = dis; head[from] = tot;}void spfa(int s){ for(int i=0;i dis[0]=0; memset(vis, 0, sizeof(vis)); vis[s] = 1; dis[s] = 0; queueQ; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for (int i = head[u]; i; i = edge[i].lat) { int to = edge[i].to; int di = edge[i].val; if (dis[to] { dis[to] = dis[u] + di; if (!vis[to]) { vis[to] = 1; Q.push(to); } } } }}int main(){ int t, x; memset(head, 0, sizeof(head)); cini(N),cini(M); while (M--) { int a, b, dis; scanf("%d %d %d", &a, &b, &dis); add(a, b, dis); } spfa(1); if(dis[N]==-INF) {return cout cout return 0;} 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net 机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
