汉寿做网站的公司,wordpress 自动登陆,温岭高端网站设计哪家好,房屋装修app拉近距离
题目背景
我是源点#xff0c;你是终点。我们之间有负权环。 ——小明
题目描述
在小明和小红的生活中#xff0c;有 N 个关键的节点。有 M 个事件#xff0c;记为一个三元组 (Si,Ti,Wi)#xff0c;表示从节点 Si 有一个事件可以转移到 Ti#xff0c;事件… 拉近距离
题目背景
我是源点你是终点。我们之间有负权环。 ——小明
题目描述
在小明和小红的生活中有 N 个关键的节点。有 M 个事件记为一个三元组 (Si,Ti,Wi)表示从节点 Si 有一个事件可以转移到 Ti事件的效果就是使他们之间的距离减少 Wi。
这些节点构成了一个网络其中节点 1 和 N 是特殊的节点 1 代表小明节点 N 代表小红其他代表进展的阶段。所有事件可以自由选择是否进行但每次只能进行当前节点邻接的。请你帮他们写一个程序计算出他们之间可能的最短距离。
输入格式
第一行两个正整数 N,M。
之后 M 行每行 3 个空格隔开的整数 Si,Ti,Wi。
输出格式
一行一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小输出Forever love。
#includebits/stdc.h
#define int long longusing namespace std;const int N 1e510;int n,m;
int suc 1;
int dis[N],vis[N],cnt[N];//长度标记经历节点数 vectorpairint,int e[N];int spfa(int A)
{for(int i1;in;i){dis[i] 1e18;vis[i] 0;cnt[i] 0;}//清空上次操作 queueint q;q.push(A);dis[A] 0;vis[A] 1;while(q.size()){int now q.front();q.pop();vis[now] 0; for(auto t:e[now]){int spot t.first,w t.second;if(dis[spot]dis[now]-w)//距离减少 {dis[spot] dis[now]-w;cnt[spot] cnt[now]1;//节点数增加 if(cnt[spot]n)//节点数大于总节点数 {suc 0;//出现负环 return false;}if(vis[spot]0)//没经历过 {vis[spot] 1;//标记 q.push(spot);}}}}return true;
}signed main()
{cinnm;while(m--){int a,b,c;cinabc;e[a].push_back({b,c});}spfa(1);int a dis[n];//小明 - 小红 经历最短距离 spfa(n);int b dis[1];//小红 - 小明 经历最短距离 if(suc0) coutForever love;//出现负环距离可以无限缩小 else coutmin(a,b);//可能的最短距离 return 0;
}邮递员送信
题目描述
有一个邮递员要送东西邮局在节点 1。他总共要送 n−1样东西其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙因此所有的道路都是单行的共有 m 条道路。这个邮递员每次只能带一样东西并且运送每件物品过后必须返回邮局。求送完这 n−1 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数n 和 m表示城市的节点数量和道路数量。
第二行到第 (m1)行每行三个整数u,v,w表示从 u 到 v 有一条通过时间为 w 的道路。
输出格式
输出仅一行包含一个整数为最少需要的时间。
#includealgorithm
#includeiostream
#includecstring
#includecstdio
#includecmath
#includequeueusing namespace std;const int M 1e610;
queueint q;int n,m,to,ta;
int u,v,w[M];
int dis1[M],dis2[M],vis[M];
int a1[M],b1[M],c1[M];
int a2[M],b2[M],c2[M];
void va1(int u,int v,int z)
{a1[to]v;b1[to]c1[u];c1[u]to;w[to]z;
}
void va2(int u,int v,int z)
{a2[ta]v;b2[ta]c2[u];c2[u]ta;w[ta]z;
}
void spfa1(int x)
{for(int i 1; in; i) {dis1[i]9999;vis[i]0;}dis1[x]0;vis[x]1;q.push(x);while(q.size()) {int nowq.front(); q.pop(); vis[now]0;for(int i c1[now]; i; ib1[i]){int ta1[i];if(dis1[t]dis1[now]w[i]){dis1[t]dis1[now]w[i];if(vis[t]0) {vis[t]1;q.push(t);}}}}
}
void spfa2(int x)
{for(int i 1;in;i) {dis2[i]9999;vis[i]0;}dis2[x]0;vis[x]1;q.push(x);while(q.size()) {int now q.front(); q.pop(); vis[now]0;for(int i c2[now]; i; ib2[i]){int ta2[i];if(dis2[t]dis2[now]w[i]) {dis2[t]dis2[now]w[i];if(vis[t]0) {vis[t]1;q.push(t);}}}}
}
int main()
{int sum10,sum20;cinnm;for(int i1; im;i){cinuvw[i];va1(u,v,w[i]);va2(v,u,w[i]);}spfa1(1);memset(vis,0,sizeof(vis));spfa2(1);for(int i1; in; i) {sum1dis1[i];sum2dis2[i];}coutsum1sum2;return 0;
} 道路重建
题目描述
从前在一个王国中在 n 个城市间有 m 条道路连接而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后有 d 条道路被破坏了。国王想要修复国家的道路系统现在有两个重要城市 A 和 B 之间的交通中断国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使 A 与 B 之间的连接恢复并要求修复的道路长度最小。
输入格式
输入文件第一行为一个整数 n (2n≤100)表示城市的个数。这些城市编号从 1 到 n。
第二行为一个整数 m (n−1≤m≤1/2n(n−1))表示道路的数目。
接下来的 m 行每行 3 个整数 i,j,k (1≤i,j≤n,i≠j,0k≤100)表示城市 i 与 j 之间有一条长为 k 的道路相连。
接下来一行为一个整数 d (1≤d≤m)表示战后被破坏的道路的数目。在接下来的 d 行中每行两个整数 i 和 j表示城市 i 与 j 之间直接相连的道路被破坏。
最后一行为两个整数 A 和 B代表需要恢复交通的两个重要城市。
输出格式
输出文件仅一个整数表示恢复 A 与 B 间的交通需要修复的道路总长度的最小值。
#includebits/stdc.h
#define fi first
#define se second
#define pb push_back
#define PII pairint,int
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);using namespace std;const int N 1e610;int n,m,d,A,B;
int dis[N];
int vis[N];
mappairint,int,int mp;
vectorpairint,int e[N];void spfa()
{for(int i 1;in;i) dis[i] 1e18;queueint q;q.push(A);dis[A] 0;vis[A] 1;while(q.size()){int now q.front();q.pop();vis[now] 0;for(auto t:e[now]){int spot t.first,w 0;if(mp[{now,spot}]1) w t.second;if(dis[spot]dis[now]w){dis[spot] dis[now]w;if(vis[spot]0){vis[spot] 1;q.push(spot);}}}}
}
signed main()
{IOS;cinnm;while(m--){int a,b,c;cinabc;e[a].push_back({b,c});e[b].push_back({a,c}); }cind;while(d--){int a,b;cinab;mp[{a,b}] 1;mp[{b,a}] 1;}cinAB;spfa();coutdis[B];return 0;
}
