7-1 ACM宣传
作者 杜祥军
单位 青岛大学
LB大神想组织集训队去学校各处宣传ACM，但是大神不想让队员们走太多路，因此想写代码计算一下，到各地宣传再回到博知401的最短路径总和是多少。
已知：学校一共有n个宣传点，博知401是标号为1的点。剩下n-1个点每个点各派1位队员，询问每个队员到达宣传点再回到博知401的最短路径和是多少。
输入格式:
输入由T个案例组成。输入的第一行只包含正整数T。
接下来是N和M，1 <= N,M <= 1000000，表示N个点和连接N个点的M条边。
然后有M行，每行包括三个值U,V,W，表示从点U到点V需要W的路程。你可以假设该图连通。
输出格式:
对于每个案例，打印一行，表示队员们从博知401出发到其他点再回到博知401的路径总和的最小值。
输入样例:
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
输出样例:
46
210
本题使用了单源最短路的想法
我使用了dijkstra算法来解决该问题
板子地址：https://www.luogu.com.cn/problem/P4779
首先从简单的开始想 每个队员从1返回到各自的位置 那么就是一个简单的dijkstra就能解决
现在再考虑每个队员从自己的位置到达1的位置的最短路 那么只需要将每个边都反转 然后从1出发即为每个点到达1的最短路
所以需要跑两遍 dijkstra
简单地思考即可得出为正边的时候跑一遍
建立返图地时候再跑一遍
建立返图时给每个点+n
code：
点击查看代码
const int maxn=1e6+10;
int n,m,cnt;
int dis[maxn],h[maxn],to[maxn],val[maxn],nxt[maxn],vis[maxn];
struct node{
int v,w;
friend bool operator <(node a,node b){
return a.w>b.w;
}
};
priority_queue<node>q;
void add(int a,int b,int c){
to[++cnt]=b;
val[cnt]=c;
nxt[cnt]=h[a];
h[a]=cnt;
}
void end(){
for(int i=0;i<=max(n<<1,m<<1);i++)to[i]=val[i]=h[i]=nxt[i]=0;
for(int i=0;i<=n<<1;i++)vis[i]=0;
}
void dijkstra(int s){
for(int i=1;i<=n<<1;i++)dis[i]=1e18;
dis[s]=0;
node tmp;
tmp.v=s;tmp.w=0;q.push(tmp);
while(!q.empty()){
int u=q.top().v;q.pop();
if(vis[u])continue;vis[u]=1;
for(int i=h[u];i;i=nxt[i]){
if(dis[to[i]]>dis[u]+val[i]){
dis[to[i]]=dis[u]+val[i];
tmp.w=dis[to[i]];
tmp.v=to[i];
q.push(tmp);
}
}
}
}
void solve(){
cnt=0;
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
add(v+n,u+n,w);
}
dijkstra(1);
int ans=0;
for(int i=2;i<=n;i++){
ans+=dis[i];
}
dijkstra(1+n);
for(int i=2+n;i<=n<<1;i++)ans+=dis[i];
cout<<ans<<'\n';
end();
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
cin>>_;
while(_--)solve();
}
请编写程序，对于给定的起始国家和目标国家，计算到达目标国家至少需要征服多少个国家，不必输出征服的国家序列，只输出征服的国家数量即可。例如下图所示的国家地图，从起始国家0到目标国家4，最少需征服2个国家。
输入格式:
输入第一行为3个整数n、e和m，均不超过1000。n表示国家数。接下来e行表示国家间的接壤情况，每行为两个整数i和j，表示国家i与国家j接壤。接下来m行表示m组查询，每行为两个整数x和y，表示起始国家和目标国家编号。
输出格式:
输出为m行，即对于给定的x和y，需要征服国家的最少数量。
输入样例:
5 6 2
0 1
0 3
1 2
2 3
1 4
2 4
0 4
1 2
输出样例:
2
1
只需按照样例建图
然后每次测试时情况vis
以x为起点 输出dis[y]的值即可
code：
点击查看代码
void solve(){
int q;
cin>>n>>m>>q;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
add(u+1,v+1,1);
add(v+1,u+1,1);
}
while(q--){
int x,y;cin>>x>>y;
for(int i=1;i<=n;i++)vis[i]=0;
dijkstra(x+1);
cout<<dis[y+1]<<'\n';
}
}//上题已经给出dijkstra和建立边的方式后面给出的code将不再显示dijkstra和建边
输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
输出格式:
输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。
输入样例:
4 4
0 1 1
0 3 1
1 3 1
2 0 1
输出样例:
1 1
板子题 注意每个数字后面一个空格 作者被空格杀了一发
code：
点击查看代码
void solve(){
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
add(u+1,v+1,w);
}
dijkstra(1);
vector<int>ans;
for(int i=2;i<=n;i++){
if(dis[i]!=1e18)ans.pb(dis[i]);
}
for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
}
7-4 哈利·波特的考试
作者 陈越
单位 浙江大学
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。
输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。
输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
输入样例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
输出样例:
4 70
本题可以用johnson(Om(n2))或者flody(On3)来做
但是没有给出m范围所以使用flody
flody运用了类似动态规划的思想
其中dis[i,j,k]表示从i-j只经过1-k内的点
对其进行分类讨论 1从i-j只经过编号为1-k-1的点的路径 那么其长度最短显然为dis[i,j,k-1]
从2 从i到k再从k到j那么长度为dis[i,k,k-1]+dis[k,j,k-1]
对其取min
其中因为每次转移可以把第三位的k优化掉
所以为节省空间考虑将转移方程优化为min(dis[i][j],dis[i][k]+dis[k][j])
其中本题想法即为枚举每个点到其他点的最大值中最小的那个
code：
点击查看代码
const int maxn=105;
int n,m,cnt;
int dis[maxn][maxn];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
if(i==j)dis[i][i]=0;
else dis[i][j]=1e18;
for(int i=1;i<=m;i++){
int x,y,val;cin>>x>>y>>val;
dis[y][x]=dis[x][y]=min(dis[x][y],val);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
int mi=1e18,pos;
for(int i=1;i<=n;i++){
int mx=0;
for(int j=1;j<=n;j++){
mx=max(dis[i][j],mx);
}
if(mx<mi){
mi=mx;
pos=i;
}
if(mx<mi){
mi=mx;
pos=i;
}
}
if(mi==1e18){
cout<<0<<'\n';return;
}
cout<<pos<<" "<<mi<<'\n';
}
我认为7-5和7-6本质一样 所以放一块讲
而且这两道题又长又臭 写的时候非常难受
7-5 最少顶点最短路
作者 朱允刚
单位 吉林大学
给定一个正权有向图，图中包含n个顶点，编号为0至n-1。以顶点0作为源点，编程序求顶点0到各顶点的最短路径。若顶点0到某顶点存在多条最短路径，则输出经过顶点最少的那条路径，例如图1，0到4的最短路径有两条，0→1→2→4和0→3→4，权值和均为6，但0→3→4经过顶点个数最少，故为所求。输入数据保证对每个顶点最多只有一条满足上述条件的路径。
GRAPH.png
输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过15000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
输出格式:
输出为若干行由“->”间隔的数字序列，每行为源点0到某顶点的满足条件的最短路径，如源点到某顶点无最短路径，则不输出该条路径。各条路径按终点的递增顺序输出，源点到源点的最短路径无需输出。
输入样例:
5 5
0 1 1
0 3 4
1 2 2
2 4 3
3 4 2
输出样例:
0->1
0->1->2
0->3
0->3->4
7-6 最少点字典序最短路径
作者 朱允刚
单位 吉林大学
给定一个正权有向图，图中包含n个顶点，编号为0至n-1。以顶点0作为源点，请编写程序求顶点0到各顶点的最短路径。若顶点0到某顶点存在多条最短路径，则输出经过顶点最少的那条路径，例如图1(a)中0到4的经过顶点最少的最短路径为0 - 3 - 4。若存在多条最短路径且其经过顶点个数相等，则输出字典序最小者。例如图1(b)中0到5的满足条件的最短路径为0 - 2 - 5。
g.jpg
注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1 2 3 9比1 2 4 5小，1 2 8 9比1 2 10 3小。
输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过20000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
输出格式:
输出为若干行由“->”间隔的数字序列，每行为源点0到某顶点的满足条件的最短路径，如源点到某顶点无最短路径，则不输出该条路径。各条路径按终点的递增顺序输出，源点到源点的最短路径无需输出。
输入样例:
6 7
0 1 1
1 4 2
4 5 3
0 3 4
3 5 2
0 2 5
2 5 1
输出样例:
0->1
0->2
0->3
0->1->4
0->2->5
首先建立depth来表示每个点的最小深度
建立pre来表示每个点的前驱节点
to[i] 表示前往的节点
点击查看代码
const int maxn=1e6+10;
int n,m,cnt;
int dis[maxn],h[maxn],to[maxn],val[maxn],nxt[maxn],vis[maxn];
struct node{
int v,w;
friend bool operator <(node a,node b){
if(a.w==b.w)return a.v>b.v;//本次如果插入很多个相同深度的节点那么节点大小升序
return a.w>b.w;
}
};
vector<int>v[20005];
int pre[20005],depth[20005];
priority_queue<node>q;
void add(int a,int b,int c){
to[++cnt]=b;
val[cnt]=c;
nxt[cnt]=h[a];
h[a]=cnt;
}//链表向前星建立图
void dijkstra(int s){
for(int i=0;i<=n;i++)dis[i]=0x3f;
for(int i=0;i<=n;i++)pre[i]=0x3f;
dis[s]=0;
node tmp;
tmp.v=s;tmp.w=0;q.push(tmp);
while(!q.empty()){
int u=q.top().v;q.pop();
if(vis[u])continue;vis[u]=1;
for(int i=h[u];i;i=nxt[i]){
if(dis[to[i]]>dis[u]+val[i]){
dis[to[i]]=dis[u]+val[i];
tmp.w=dis[to[i]];
tmp.v=to[i];
depth[to[i]]=depth[u]+1;
pre[to[i]]=u;
q.push(tmp);
}
else if(dis[to[i]]==dis[u]+val[i]){
if(depth[u]+1<depth[to[i]]){
depth[to[i]]=depth[u]+1;
pre[to[i]]=u;
q.push(node{to[i],dis[to[i]]});
}else if(depth[u]+1==depth[to[i]]){
int a=u;
int b=pre[to[i]];
while(pre[a]!=pre[b]){
a=pre[a],b=pre[b];
}
if(a<b){
pre[to[i]]=u;
q.push(node{to[i],dis[to[i]]});
}
}
}
}
}
}
void solve(){
cin>>n>>m;
for(int i=1,u,t,w;i<=m;i++){
cin>>u>>t>>w;
add(u+1,t+1,w);
}//通过+1防止越界出错
dijkstra(1);
for(int i=2;i<=n;i++){
int j=i;
while(j!=1){//如果不到第一个节点不结束
if(pre[j]==0x3f)break;//如果找不到前继节点就结束 该种情况为不连通
v[i].pb(j);
j=pre[j];
}
}
for(int i=2;i<=n;i++){
if(v[i].size()){
cout<<0;
for(int j=v[i].size()-1;j>=0;j--){
cout<<"->"<<v[i][j]-1;
}
cout<<'\n';
}
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--)solve();
}
输入格式:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。
每组测试包含两个部分。分别是： 景点信息 和 查询。
景点信息 部分,首先是2个整数n和m（2≤n≤100，1≤m≤n(n-1)/2），分别表示有n个景点，以及m条直达道路的用时信息。然后有m行输入，每行输入三个整数a,b,c（1≤a,b≤n，a≠b，1≤c<100），表示由景点a散步到景点b，HY散步需要用时c分钟，当然，他由景点b散步到景点a也要c分钟。
查询 部分，首先是1个整数k（1<=k<=5000），表示后面接k次询问。紧接着k行数据，每行包括两个整数s,d（1≤s，d≤n，s≠d），分别表示HY想知道从景点s散步到另一个景点d的用时（分钟数）。
注意，因为HY有点粗心，可能发生以下情况：
（1）他所记下有些用时信息可能重复，比如：
1 2 3
2 1 3
（2）有些同一条路的用时信息可能不一致，比如：
1 2 3
1 2 4
在这种情况下，以其中用时最少的信息为准。
（3）有些路用时信息可能忘记了，比如有3个景点1，2，3；他只记住1条路的用时：
1 2 1
在这种情况下，认为从景点1到景点3没有直达的路，从景点2到景点3也没有直达的路。
输出格式:
对于每组测试，每次询问输出一行，包含一个整数，表示从景点s散步到另一个景点d的最少用时。如果景点s到景点d无路可通，输出-1。
输入样例:
2
3 2
1 2 3
2 3 1
3
1 2
1 3
3 2
3 2
1 2 3
2 1 2
3
1 2
1 3
2 3
输出样例:
3
4
1
2
-1
-1
非常简单的一道flody板子题
不多解释
code：
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
const int maxn=105;
int n,m,cnt;
int dis[maxn][maxn];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
if(i==j)dis[i][i]=0;
else dis[i][j]=1e18;
for(int i=1;i<=m;i++){
int x,y,val;cin>>x>>y>>val;
dis[y][x]=dis[x][y]=min(dis[x][y],val);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
int q;cin>>q;
while(q--){
int s,d;cin>>s>>d;
if(dis[s][d]==1e18)cout<<-1<<'\n';
else cout<<dis[s][d]<<'\n';
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
cin>>_;
while(_--)solve();
}