集团网站建设特点 互联网课堂,网页源代码在线查看,医院网站 功能,东莞公司注册可以用住宅吗1135. 新年好 题目 提交记录 讨论 题解 视频讲解 MarkDown视图Copy
重庆城里有 nn 个车站#xff0c;mm 条 双向 公路连接其中的某些车站。
每两个车站最多用一条公路连接#xff0c;从任何一个车站出发都可以经过一条或者多条公路到达其他车站#xff0c;但不同的…1135. 新年好 题目 提交记录 讨论 题解 视频讲解 MarkDown视图Copy
重庆城里有 nn 个车站mm 条 双向 公路连接其中的某些车站。
每两个车站最多用一条公路连接从任何一个车站出发都可以经过一条或者多条公路到达其他车站但不同的路径需要花费的时间可能不同。
在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 11他有五个亲戚分别住在车站 a,b,c,d,ea,b,c,d,e。
过年了他需要从自己的家出发拜访每个亲戚顺序任意给他们送去节日的祝福。
怎样走才需要最少的时间
输入格式
第一行包含两个整数 n,mn,m分别表示车站数目和公路数目。
第二行包含五个整数 a,b,c,d,ea,b,c,d,e分别表示五个亲戚所在车站编号。
以下 mm 行每行三个整数 x,y,tx,y,t表示公路连接的两个车站编号和时间。
输出格式
输出仅一行包含一个整数 TT表示最少的总时间。
数据范围
1≤n≤500001≤n≤50000, 1≤m≤1051≤m≤105, 1a,b,c,d,e≤n1a,b,c,d,e≤n, 1≤x,y≤n1≤x,y≤n, 1≤t≤1001≤t≤100
输入样例
Copy
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7输出样例
Copy
21
#includeiostream
#includecstring
#includequeue
#define pii pairint,int
using namespace std;
#define INF 0x3f3f3f3f
const int M100010;const int N50010;
struct EDGE{int next;int to;int w;
}edge[2*M];int tot0;
int n,m;int head[N];
void add(int u,int v,int w){edge[tot].nexthead[u];edge[tot].tov;edge[tot].ww;head[u]tot;
}int ansINF;
int A[6];
int dis[6][6];
void dijk(int ss){int sA[ss];int dist[N];bool st[N]{0};memset(dist,INF,sizeof(dist));priority_queuepii,vectorpii,greaterpiiheap;heap.push({0,s});dist[s]0;while(!heap.empty()){pii tempheap.top();heap.pop();int xtemp.first;int ytemp.second;if(st[y])continue;st[y]1;for(int ihead[y];~i;iedge[i].next){//coutjinendl;int vedge[i].to;if(dist[v]xedge[i].w){dist[v]xedge[i].w;heap.push({dist[v],v});}}}for(int i0;i5;i){dis[ss][i]dis[i][ss]dist[A[i]];}
}int B[6];bool book[6];
void dfs(int step){if(step6){int res0;//coutB;for(int i1;i5;i){// 1 2 3 4 5dfs编号//B 亲戚 1 2 3 4 5 编号//A 结点编号//coutA[B[i]] ;//coutdis[B[i-1]][B[i]] ;resdis[B[i-1]][B[i]];}//coutresendl;ansmin(ans,res);return ;}for(int i1;i5;i){if(!book[i]){book[i]1;B[step]i;dfs(step1);book[i]0;}}}int main(){cinnm;memset(head,-1,sizeof(head));A[0]1;for(int i1;i5;i)cinA[i];while(m--){int u,v,w;cinuvw;add(u,v,w);add(v,u,w);}for(int i0;i5;i){dijk(i);}B[0]0;dfs(1);coutansendl;} 340. 通信线路 题目 提交记录 讨论 题解 视频讲解 MarkDown视图Copy
在郊区有 NN 座通信基站PP 条 双向 电缆第 ii 条电缆连接基站 AiAi 和 BiBi。
特别地11 号基站是通信公司的总站NN 号基站位于一座农场中。
现在农场主希望对通信线路进行升级其中升级第 ii 条电缆需要花费 LiLi。
电话公司正在举行优惠活动。
农产主可以指定一条从 11 号基站到 NN 号基站的路径并指定路径上不超过 KK 条电缆由电话公司免费提供升级服务。
农场主只需要支付在该路径上剩余的电缆中升级价格最贵的那条电缆的花费即可。
求至少用多少钱可以完成升级。
输入格式
第 11 行三个整数 NPKNPK。
第 2..P12..P1 行第 i1i1 行包含三个整数 Ai,Bi,LiAi,Bi,Li。
输出格式
包含一个整数表示最少花费。
若 11 号基站与 NN 号基站之间不存在路径则输出 −1−1。
数据范围
0≤KN≤10000≤KN≤1000, 1≤P≤100001≤P≤10000, 1≤Li≤10000001≤Li≤1000000
输入样例
Copy
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6输出样例
Copy
4难度中等时/空限制1s / 64MB总通过数14023总尝试数27405来源 《算法竞赛进阶指南》USACO2008 算法标签
分层图
#includeiostream
using namespace std;
#includecstring#define ll long long
#define INF 0x3f3f3f3f
#includequeue
#define pll pairll,ll
ll n,m,k;
const ll M10010*4*1010;
const ll N1010*1010;
struct EDGE{ll next;ll to;ll w;
}edge[2*M];
ll head[N];ll tot0;
void add(ll u,ll v,ll w){
edge[tot].nexthead[u];
edge[tot].tov;
edge[tot].ww;
head[u]tot;
}ll dist[N];bool st[N];
void dijk(ll s){memset(dist,INF,sizeof(dist));priority_queuepll,vectorpll,greaterpll heap;heap.push({0,s});dist[s]0;while(!heap.empty()){pll tempheap.top();heap.pop();ll dtemp.first;ll utemp.second;if(st[u])continue;st[u]1;for(ll ihead[u];~i;iedge[i].next){ll vedge[i].to;//一个可以被更新dist[v]//被更新为多少max(d,)if(dist[v]max(d,edge[i].w)){dist[v]max(d,edge[i].w);heap.push({dist[v],v});}}}
}int main(){cinnmk;memset(head,-1,sizeof(head));while(m--){ll u,v,w;cinuvw;for(ll j1;jk;j){add(u(j-1)*n,vj*n,0);add(v(j-1)*n,uj*n,0);}for(ll j0;jk;j){add(uj*n,vj*n,w);add(vj*n,uj*n,w);}}dijk(1);ll ansINF;for(ll j0;jk;j){ansmin(ans,dist[nj*n]);}coutans;
}二分dijk
#includeiostream
using namespace std;
#includequeue
#define pii pairint,int
#define INF 0x3f3f3f3f
#includecstring
const int M10010;
const int N1010;
int n,m,k;
struct EDGE{int next;int to;int w;
}edge[2*M];
int head[N];int tot0;
void add(int u,int v,int w){edge[tot].nexthead[u];edge[tot].tov;edge[tot].ww;head[u]tot;
}bool check(int mid){priority_queuepii,vectorpii,greaterpii heap;bool st[N]{0};int dist[N];memset(dist,INF,sizeof(dist));heap.push({0,1});dist[1]0;while(!heap.empty()){pii tempheap.top();heap.pop();int dtemp.first;int utemp.second;if(st[u])continue;st[u]1;for(int ihead[u];~i;iedge[i].next){int vedge[i].to;int w(edge[i].wmid);if(dist[v]dw){dist[v]dw;heap.push({dist[v],v});}}}//mid大比他大的就会少return dist[n]k;}int main()
{memset(head,-1,sizeof(head));cinnmk;while(m--){int u,v,w;cinuvw;add(u,v,w);add(v,u,w);}int l0,r1e710;while(lr){int mid(lr)1;if(check(mid))rmid;else lmid1;}if(l1e710)cout-1;else coutl;
} 342. 道路与航线 题目 提交记录 讨论 题解 视频讲解 MarkDown视图Copy
农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。
他想把牛奶送到 TT 个城镇编号为 1∼T1∼T。
这些城镇之间通过 RR 条道路 (编号为 11 到 RR) 和 PP 条航线 (编号为 11 到 PP) 连接。
每条道路 ii 或者航线 ii 连接城镇 AiAi 到 BiBi花费为 CiCi。
对于道路0≤Ci≤10,0000≤Ci≤10,000;然而航线的花费很神奇花费 CiCi 可能是负数(−10,000≤Ci≤10,000−10,000≤Ci≤10,000)。
道路是双向的可以从 AiAi 到 BiBi也可以从 BiBi 到 AiAi花费都是 CiCi。
然而航线与之不同只可以从 AiAi 到 BiBi。
事实上由于最近恐怖主义太嚣张为了社会和谐出台了一些政策保证如果有一条航线可以从 AiAi 到 BiBi那么保证不可能通过一些道路和航线从 BiBi 回到 AiAi。
由于约翰的奶牛世界公认十分给力他需要运送奶牛到每一个城镇。
他想找到从发送中心城镇 SS 把奶牛送到每个城镇的最便宜的方案。
输入格式
第一行包含四个整数 T,R,P,ST,R,P,S。
接下来 RR 行每行包含三个整数表示一个道路Ai,Bi,CiAi,Bi,Ci。
接下来 PP 行每行包含三个整数表示一条航线Ai,Bi,CiAi,Bi,Ci。
输出格式
第 1..T1..T 行第 ii 行输出从 SS 到达城镇 ii 的最小花费如果不存在则输出 NO PATH。
数据范围
1≤T≤250001≤T≤25000, 1≤R,P≤500001≤R,P≤50000, 1≤Ai,Bi,S≤T1≤Ai,Bi,S≤T
输入样例
Copy
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10输出样例
Copy
NO PATH
NO PATH
5
0
-95
-100
