A. 最短路径问题

模板题。

#include<bits/stdc++.h>
using namespace std;
int ans,n,m,s,t,mini;
double g[1001][1001],lost[1010],mn;
bool b[1101];
int x[1001],y[1001];
void mst()
{
memset(lost,0x7f,sizeof lost);
memset(b,1,sizeof(b));
lost[s]=0;
while(1) {
mn=INT_MAX;
for(int i=1; i<=n; i++)
{
if(b[i]&&lost[i]<mn)
{
mn=lost[i];
mini=i;
}
}
if(mn==INT_MAX)break;
b[mini]=false;
for(int i=1; i<=n; i++)
{
if(b[i]&&g[mini][i]+lost[mini]<lost[i])
lost[i]=g[mini][i]+lost[mini];
}
}
printf("%.2lf",lost[t]);
}
int main() {
memset(g,0x7f,sizeof(g));
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d%d",&x[i],&y[i]);
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
g[a][b]=g[b][a]=sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
}
scanf("%d%d",&s,&t);
mst();
return 0;
}

B. Heat Wave 热浪

模板题。

#include<bits/stdc++.h>
using namespace std;
const int N=107;
int x[N],y[N],from[N*N],to[N*N];
int edge[N*N],dis[N*N];
int main()
{
int n,m,s,t;
scanf("%d",&n);
scanf("%d",&m); scanf("%d%d",&s,&t);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
from[i]=a,to[i]=b;
edge[i]=c;
}
memset(dis,63,sizeof(dis));
dis[s]=0;
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
if(dis[to[j]]>dis[from[j]]+edge[j])dis[to[j]]=dis[from[j]]+edge[j];
if(dis[from[j]]>dis[to[j]]+edge[j])dis[from[j]]=dis[to[j]]+edge[j];
}
}
printf("%d",dis[t]);
return 0;
}

C. Hide and Seek 捉迷藏

堆优化，模板题。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int f[N],vis[N],last[N];
int cnt,mx=INT_MIN,ans;
struct data
{
int u,dist;
};
bool operator <(data a,data b)
{
return a.dist>b.dist;
}
struct edge
{
int to,next;
}e[N];
void add(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void mst()
{
priority_queue<data> q;
data temp;
temp.u=1;
temp.dist=0;
q.push(temp);
while(!q.empty())
{
temp=q.top();
q.pop();
int now=temp.u;
if(vis[now])continue;
vis[now]=1;
for(int i=last[now];i;i=e[i].next)
{
if(f[now]+1<f[e[i].to])
{
f[e[i].to]=f[now]+1;
temp.u=e[i].to;
temp.dist=f[e[i].to];
q.push(temp);
}
}
}
}
int main() {
int n,m;
memset(f,63,sizeof(f));
f[1]=0;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) {
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
mst();
for(int i=1; i<=n; i++)
mx=max(mx,f[i]);
for(int i=1; i<=n; i++)
{
if(mx==f[i])
{
ans++;
if(ans==1)
printf("%d ",i);
}
}
printf("%d %d",mx,ans);
return 0;
}

D. Chocolate Giving

堆优化，模板题。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int f[N],vis[N],last[N];
int cnt,mx=INT_MIN,ans;
struct data
{
int u,dist;
};
bool operator <(data a,data b)
{
return a.dist>b.dist;
}
struct node
{
int to,next,edge;
}e[N];
void add(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].edge=w;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].edge=w;
}
void mst()
{
priority_queue<data> q;
data temp;
temp.u=1;
temp.dist=0;
q.push(temp);
while(!q.empty())
{
temp=q.top();
q.pop();
int now=temp.u;
if(vis[now])continue;
vis[now]=1;
for(int i=last[now];i;i=e[i].next)
{
if(f[now]+e[i].edge<f[e[i].to])
{
f[e[i].to]=f[now]+e[i].edge;
temp.u=e[i].to;
temp.dist=f[e[i].to];
q.push(temp);
}
}
}
}
int main()
{
int n,m,k;
memset(f,63,sizeof(f));
f[1]=0;
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=m; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
mst();
for(int i=1;i<=k;i++)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",f[a]+f[b]);
}
return 0;
}

E. Best Spot 最佳牧场

多源最短路。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int f[N],vis[N],last[N],t[N];
int cnt,minn=INT_MAX,ans;
int n,m,k;
struct data
{
int u,dist;
};
bool operator <(data a,data b)
{
return a.dist>b.dist;
}
struct node
{
int to,next,edge;
}e[N];
void add(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].edge=w;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].edge=w;
}
int mst(int x)
{
memset(f,63,sizeof(f));
memset(vis,0,sizeof(vis));
f[x]=0;
int sum=0;
priority_queue<data> q;
data temp;
temp.u=x;
temp.dist=0;
q.push(temp);
while(!q.empty())
{
temp=q.top();
q.pop();
int now=temp.u;
if(vis[now])continue;
vis[now]=1;
for(int i=last[now];i;i=e[i].next)
{
if(f[now]+e[i].edge<f[e[i].to])
{
f[e[i].to]=f[now]+e[i].edge;
temp.u=e[i].to;
temp.dist=f[e[i].to];
q.push(temp);
}
}
}
for(int i=1;i<=n;++i)
{
if(f[t[i]]==INT_MAX)return INT_MAX;
sum+=f[t[i]];
}
return sum;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
scanf("%d",&t[i]);
for(int i=1; i<=k; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
for(int i=1;i<=n;i++)
{
int p=mst(i);
if(p<minn)
{
minn=p;
ans=i;
}
}
printf("%d",ans);
return 0;
}

F. Cow Hurdles 奶牛跨栏

多源最短路。

#include<bits/stdc++.h>
using namespace std;
int f[1001][1001];
int main()
{
memset(f,63,sizeof(f));
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
f[x][y]=z;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(max(f[i][k],f[k][j]),f[i][j]);
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(f[x][y]==1061109567)
puts("-1");
else
printf("%d\n",f[x][y]);
}
return 0;
}

G. 最短路上的统计

多源最短路。

#include<bits/stdc++.h>
using namespace std;
int f[101][101],ans[101][101];
int main()
{
int n,m,p;
memset(f,63,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
f[i][i]=0;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
f[x][y]=f[y][x]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(f[i][j]==f[i][k]+f[k][j])
ans[i][j]++;
}
scanf("%d",&p);
for (int i=1;i<=p;i++)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",ans[x][y]);
}
return 0;
}

H. Roadblocks 次短路

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int f[N],vis[N],last[N],f1[N];
int cnt,mx=INT_MIN,ans;
struct data {
int u,dist;
};
bool operator <(data a,data b) {
return a.dist>b.dist;
}
struct node {
int to,next,edge;
} e[N];
void add(int u,int v,int w) {
e[++cnt].to=v;
e[cnt].next=last[u];
last[u]=cnt;
e[cnt].edge=w;
e[++cnt].to=u;
e[cnt].next=last[v];
last[v]=cnt;
e[cnt].edge=w;
}
void mst() {
priority_queue<data> q;
data temp;
temp.u=1;
temp.dist=0;
q.push(temp);
while(!q.empty()) {
temp=q.top();
q.pop();
int now=temp.u;
for(int i=last[now]; i; i=e[i].next) {
/*
f[now]......du
w...........e[i].edge
v...........e[i].to
*/
bool flag=false;
if(f[now]+e[i].edge<f[e[i].to]) {
f[e[i].to]=f[now]+e[i].edge;
flag=true;
}
if(f[now]+e[i].edge>f[e[i].to]&&f[now]+e[i].edge<f1[e[i].to]) {
f1[e[i].to]=f[now]+e[i].edge;
flag=true;
}
if(f1[now]+e[i].edge<f1[e[i].to]) {
f1[e[i].to]=f1[now]+e[i].edge;
flag=true;
}
if(flag==true)
{
temp.u=e[i].to;
temp.dist=f[e[i].to];
q.push(temp);
}
}
}
}
int main() {
int n,m;
memset(f,63,sizeof(f));
memset(f1,63,sizeof(f1));
f[1]=0;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
mst();
printf("%d",f1[n]);
return 0;
}