网上订货发货网站建设,wordpress标签生成,网站推广策划方案书,中山门户网站制作在哪里买差分约束裸题#xff0c;用了比较蠢的方法#xff0c;先dfs_spfa判负环#xff0c;再bfs_spfa跑最短路 注意到“奶牛排在队伍中的顺序和它们的编号是相同的”#xff0c;所以\( d_i-d_{i-1}0 \),连(i,i-1,0)#xff1b;然后对于\( d_i-d_jL \)#xff0c;连(j,i,…差分约束裸题用了比较蠢的方法先dfs_spfa判负环再bfs_spfa跑最短路 注意到“奶牛排在队伍中的顺序和它们的编号是相同的”所以\( d_i-d_{i-1}0 \),连(i,i-1,0)然后对于\( d_i-d_jL \)连(j,i,L)对于\( d_i-d_jD -- d_j-d_i-D \)连i,j,-D 然后先判负环再跑最短路即可 #includeiostream
#includecstdio
#includequeue
#includecstring
using namespace std;
const int N100005,inf1e9;
int n,l,d,h[N],cnt,dis[N];
bool v[N],flg;
struct qwe
{int ne,to,va;
}e[N*3];
int read()
{int r0,f1;char pgetchar();while(p9||p0){if(p-)f-1;pgetchar();}while(p0p9){rr*10p-48;pgetchar();}return r*f;
}
void add(int u,int v,int w)
{cnt;e[cnt].neh[u];e[cnt].tov;e[cnt].vaw;h[u]cnt;
}
void spfa(int u)
{if(flg)return;v[u]1;for(int ih[u];i;ie[i].ne)if(dis[e[i].to]dis[u]e[i].va){if(v[e[i].to]){flg1;return;}else{dis[e[i].to]dis[u]e[i].va;spfa(e[i].to);}}v[u]0;
}
int main()
{nread(),lread(),dread();for(int i1;il;i){int xread(),yread(),zread();add(x,y,z);}for(int i1;id;i){int xread(),yread(),zread();add(y,x,-z);}for(int i2;in;i)add(i,i-1,0);for(int i1;in!flg;i)spfa(i);if(flg){puts(-1);return 0;}memset(v,0,sizeof(v));for(int i1;in;i)dis[i]inf;queueintq;v[1]1,dis[1]0,q.push(1);while(!q.empty()){int uq.front();q.pop();v[u]0;for(int ih[u];i;ie[i].ne)if(dis[e[i].to]dis[u]e[i].va){dis[e[i].to]dis[u]e[i].va;if(!v[e[i].to]){v[e[i].to]1;q.push(e[i].to);}}}printf(%d\n,dis[n]inf?-2:dis[n]);return 0;
} 转载于:https://www.cnblogs.com/lokiii/p/9191549.html
