#pragma once
#include"../graph/graph-template.hpp"template<typenameT>structDual_of_Shortest_Path{intN;vector<edge<T>>es;Dual_of_Shortest_Path(int_n):N(_n){}// add constraint f(j) <= f(i) + wvoidadd_edge(inti,intj,Tc){es.emplace_back(i,j,c);}// if s != -1, solve max{f(t) - f(s)} for each t// if unsatisfiable, return empty vectorvector<T>solve(intstart=-1){TINF=numeric_limits<T>::max()/2.1;vector<T>d(N,INF);if(start==-1)fill(begin(d),end(d),T{0});if(start!=-1)d[start]=0;for(intloop=0;loop<N;loop++){intupd=0;for(autoe:es){if(d[e.src]+e.cost<d[e.to]){d[e.to]=d[e.src]+e.cost;upd=1;}}if(!upd)break;if(loop==N-1)return{};}returnd;}};/**
* @brief 牛ゲー(最短路問題の双対)
*/
#line 2 "shortest-path/dual-of-shortest-path.hpp"
#line 2 "graph/graph-template.hpp"
template<typenameT>structedge{intsrc,to;Tcost;edge(int_to,T_cost):src(-1),to(_to),cost(_cost){}edge(int_src,int_to,T_cost):src(_src),to(_to),cost(_cost){}edge&operator=(constint&x){to=x;return*this;}operatorint()const{returnto;}};template<typenameT>usingEdges=vector<edge<T>>;template<typenameT>usingWeightedGraph=vector<Edges<T>>;usingUnweightedGraph=vector<vector<int>>;// Input of (Unweighted) GraphUnweightedGraphgraph(intN,intM=-1,boolis_directed=false,boolis_1origin=true){UnweightedGraphg(N);if(M==-1)M=N-1;for(int_=0;_<M;_++){intx,y;cin>>x>>y;if(is_1origin)x--,y--;g[x].push_back(y);if(!is_directed)g[y].push_back(x);}returng;}// Input of Weighted Graphtemplate<typenameT>WeightedGraph<T>wgraph(intN,intM=-1,boolis_directed=false,boolis_1origin=true){WeightedGraph<T>g(N);if(M==-1)M=N-1;for(int_=0;_<M;_++){intx,y;cin>>x>>y;Tc;cin>>c;if(is_1origin)x--,y--;g[x].emplace_back(x,y,c);if(!is_directed)g[y].emplace_back(y,x,c);}returng;}// Input of Edgestemplate<typenameT>Edges<T>esgraph([[maybe_unused]]intN,intM,intis_weighted=true,boolis_1origin=true){Edges<T>es;for(int_=0;_<M;_++){intx,y;cin>>x>>y;Tc;if(is_weighted)cin>>c;elsec=1;if(is_1origin)x--,y--;es.emplace_back(x,y,c);}returnes;}// Input of Adjacency Matrixtemplate<typenameT>vector<vector<T>>adjgraph(intN,intM,TINF,intis_weighted=true,boolis_directed=false,boolis_1origin=true){vector<vector<T>>d(N,vector<T>(N,INF));for(int_=0;_<M;_++){intx,y;cin>>x>>y;Tc;if(is_weighted)cin>>c;elsec=1;if(is_1origin)x--,y--;d[x][y]=c;if(!is_directed)d[y][x]=c;}returnd;}/**
* @brief グラフテンプレート
* @docs docs/graph/graph-template.md
*/#line 4 "shortest-path/dual-of-shortest-path.hpp"
template<typenameT>structDual_of_Shortest_Path{intN;vector<edge<T>>es;Dual_of_Shortest_Path(int_n):N(_n){}// add constraint f(j) <= f(i) + wvoidadd_edge(inti,intj,Tc){es.emplace_back(i,j,c);}// if s != -1, solve max{f(t) - f(s)} for each t// if unsatisfiable, return empty vectorvector<T>solve(intstart=-1){TINF=numeric_limits<T>::max()/2.1;vector<T>d(N,INF);if(start==-1)fill(begin(d),end(d),T{0});if(start!=-1)d[start]=0;for(intloop=0;loop<N;loop++){intupd=0;for(autoe:es){if(d[e.src]+e.cost<d[e.to]){d[e.to]=d[e.src]+e.cost;upd=1;}}if(!upd)break;if(loop==N-1)return{};}returnd;}};/**
* @brief 牛ゲー(最短路問題の双対)
*/