SSSP.cpp

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define f(i,a,b) for(int (i)=int (a);i<=int (b);i++)
#define ff(i,a,b) for(int (i)=int (a);i<int (b);i++)
#define F(i,a,b) for(int (i)=int (a);i>=int (b);i--)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define ll long long
#define  ld long double
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
const double eps=1e-9,pi=acos(-1.0);
const int N=1e6+6,inf=0x3f3f3f3f,mod=1e9+7;
void dijkstra(){
	int V,E,s;
	cin>>V>>E>>S;
	vector<vii> g(V,vii());
	while(E--){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].emplace_back(v,w);
	}
	vi dist(V,inf);dist[s]=0;
	// original dijkstra
/*	set<ii> pq;
	ff(u,0,q)
		pq.insert({dist[u],u});
	while(!pq.empty()){
		auto [d,u]=*pq.begin();
		pq.erase(pq.begin());
		for(auto &[v,w]:g[u]){
			if(dist[u]+w>=dist[v]) continue;
			pq.erase(pq.find({dist[v],v}));
			dist[v]=dist[u]+w;
			pq.insert({dist[v],v});
		}
	} */
	priority_queue<ii,vector<ii>,greater<ii> >pq.
	pq.push({0,s});
	while(!pq.empty()){
		auto [d,u]=pq.top();pq.pop();
		if(d>dist[u]) continue;
		for(auto &[v,w]:g[u]){
			if(dist[u]+w>=dist[v]) continue;
			dist[v]=dist[u]+w;
			pq.push({dist[v],v});
		}
	}
	
}
void bellman_ford(){
	int V,E,s;
	cin>>V>>E>>s;
	while(E--){
		int u,v,w;cin>>u>>v>>w;
		g[u].emplace_back(v,w);
	}
	vi dist(V,inf);dist[s]=0;
	for(int i=0;i<V-1;i++){
		bool modified=false;
		for(int u=0;u<V;u++){
			if(dist[u]!=inf){
				for(auto &[v,w]:g[u]){
					if(dist[u]+w>=dist[v]) continue;
					dist[v]=dist[u]+w;
					modified=true;
				}
			}
		}
		if(!modified) break;
	}
	bool hasNegativeCycle=false;
	for(int u=0;u<V;u++){
		if(dist[u]!=inf){
			for(auto &[v,w]:g[u]){
				if(dist[v]>dist[u]+w){
					hasNegativeCycle=true;
				}
			}
		}
	}
}