最短路
题意：就是让我们求从商场到赛场的最短距离
我们先来看下暴力解法~
1.我们首先建立一个邻接矩阵mapt来表示从 i 到 j 存在一条路；
2.首先我们知道在给这个mapt初始化时在主对角线上的元素，及
i == j ,表示的是从自身到自身，那么我们自然要给其初始化为0，
其余的我们统统看成没有路，即为INF。
3.然后我们要输入题目中所给的路径，因为由题意我们要构造的图应该是无向的，所以从i 到 j和从 j 到 i 应该路径都是相同的。
4.在这之后，自然是将所有可能的结果都计算然后从中取最小值即可。（最外面的一层应该是中间端点，随后两个for是两端点）
如果多走一个节点能使距离减少，那么我们自然要将此时从i到j的最短距离更新了。
5.然后我们就能得到从任意端点到任意端点的最短距离了，存在mapt中，我们按照题意输出即可~~
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 105
int mapt[maxn][maxn];
int main(){
int n,m;
while(cin>>n>>m && n+m){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j){
mapt[i][j] = 0;
}
else
mapt[i][j] = inf;
}
int x,y,z;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
if(mapt[x][y]>z)
mapt[x][y]= mapt[y][x] = z;
}
for(int k =1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(mapt[i][j]>mapt[i][k]+mapt[k][j])
mapt[i][j]=mapt[i][k]+mapt[k][j];
}
cout<<mapt[1][n]<<endl;
}
return 0;
}
然后欣赏完暴力学的美感后，我们来看一下如何优化。
dijsktra算法~~(单源最短路径，只能处理正权的边)
运行时间整整少了一半呢！！是不是很感人~(⊙o⊙)…
#include <iostream>
using namespace std;
#define inf 0x3f3f3f3f//无限大
int map[105][105],dis[105],vis[105];//mapt作用同上用来存图，dis表示最短距离，vis表示是否访问过~
int n,m;
void dijkstra(int start) //重点还是dijsktra这个函数，处理的是将dis更新为能存在的最短路径~
{
int i,j,k;
for(i=1; i<=n; i++)//这里相当于对这个dis进行初始化
{
dis[i]=map[start][i];
}
for(i=1;i<=n;i++)
vis[i]=0;//访问过得话为1，没有访问过得话为0; vis的初始化 ；
vis[start]=1;//因为我们是从这里开始的，所以可以直接记为1.表示访问过了。
for(i=1;i<=n-1;i++) //这个位置呢，是我们遍历端点（建议看下理论推导过程后再看，本博客只详细讲解代码）
{
int mix=inf;
int u;
for(j=1;j<=n;j++)
{
if(vis[j]==0 && mix>dis[j])//我们将所有的边遍历，然后从中找到与start相通的最短的那一个
{
mix=dis[j];//我们将其更新为最短路径
u=j;//标记
}
}
vis[u]=1;//更新为访问过了
for(k=1;k<=n;k++)//可能有些端点经过更多点后距离变得更短了
{
if(vis[k]==0 && dis[k]>dis[u]+map[u][k])
dis[k]=dis[u]+map[u][k];
}
}//注意第一个for循环得结尾在这里！
}
int main()
{
int i,j,k;
while(cin>>n>>m && n || m)
{
for(i=1;i<=n;i++)//这一部分依然是存图~
for(j=1;j<=n;j++)
{
if(i==j)
map[i][j]=0;
else
map[i][j]=inf;
}
while(m--)//这里是路径的输入
{
int x,y,z;
cin>>x>>y>>z;
if(map[x][y]>z)
{
map[x][y]=map[y][x]=z; //无向图
}
}
dijkstra(1);//这里表示从1开始求到各顶点的最短距离~
cout<<dis[n]<<endl;//想求哪个直接输出就行了~
}
return 0;
}
题意：意思大概就是他想睡懒觉，然后要早点回去，你要找到一个最短的路让他回去，是不是很有用的算法啊~
你看完后肯定说！哇，几乎一模一样哎！对哦，这是最简单的模范题哦，把这些深刻领会了，再加上你自己的聪明才智，ACM金牌爷就是您啊！！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 0x3f3f3f3f
using namespace std ;
int u , v ,n, dis[1111],vis[1111],ma[1111][1111];
void dijk()
{
int k , mini;
for(int i = 1 ; i <=v;i++)
{
dis[i]=ma[1][i];
}
for(int i = 1 ;i<=v;i++)
{
mini=MAX;
for(int j = 1 ; j<=v;j++)
{
if(!vis[j]&&dis[j]<mini)
{
mini=dis[j];
k=j;
}
}
vis[k]=1;
for(int j=1 ;j<=v;j++)
{
if(dis[j]>dis[k]+ma[k][j])
{
dis[j]=dis[k]+ma[k][j];
}
}
}
}
int main()
{
while(cin>>u>>v)
{
n=0;
for(int i = 0 ; i <=v;i++)
{
for(int j = 0 ; j <=v;j++)
{
ma[i][j] = MAX;
}
ma[i][i]=0;
vis[i]=0;
dis[i]=MAX;
}//这里是所有的初始化，我感觉这样写很吊的感觉~嘿嘿嘿
for(int i = 1;i<=u;i++)
{
int a , b , len;
cin>>a>>b>>len;
n=max(max(n,a),b);
if(ma[a][b]>len)
{
ma[a][b]=ma[b][a]=len;
}
}
dijk();
printf("%d\n",dis[v]);
}
return 0 ;
}
B - 畅通工程续
题意：这不就是找路最短嘛！！！
这该死的模板，这样在练不会就没脸泡妞了！！！（你说似吧）
#include<bits/stdc++.h>
using namespace std;
#define N 205
#define inf 0x3f3f3f3f
int dis[N],w[N][N],n,m,x,y;
bool vis[N];
void dijstra()
{
int i,j;
for(i=0;i<n;i++)
{
dis[i]=w[x][i];
vis[i]=0;
}
dis[x]=0;
vis[x]=1;
for(i=0;i<n;i++)
{
int mark,mindis=inf;
for(j=0;j<n;j++)
{
if(!vis[j]&&dis[j]<mindis)
{
mindis=dis[j];
mark=j;
}
}
//if(mindis==inf) break;
vis[mark]=1;
for(j=0;j<n;j++)
{
if(!vis[j])
{
dis[j]=min(dis[j],dis[mark]+w[mark][j]);
}
}
}
if(dis[y]==inf)
printf("-1\n");
else printf("%d\n",dis[y]);
}
void init()
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
w[i][j]=inf;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int i,a,b,c;
init();
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c<w[a][b]) w[a][b]=w[b][a]=c;
}
scanf("%d%d",&x,&y);
dijstra();
}
return 0;
}
Currency Exchange
那你肯定说：遇到负权问题怎么办啊！？
你怎么就这么好学呢！！！
程序学好就能有女朋友！
什么？！！！
那让我们来一起为将来的那个可爱的女孩努力钻研这深奥的代码吧！毕竟我们的头发能给她换来mo+++.
#include<iostream>
using namespace std;
double dis[109];
int tol;
int R[209][2];
double C[209][2];
bool Bellman( int s ,int n ,double v ){
for( int i=1;i<=n;i++)
dis[i] = 0;
dis[s] = v;
for( int i=1;i<n;i++){
bool flag = false;
for( int j=0;j<tol;j++){
int u = R[j][0];
int v = R[j][1];
if( dis[v] < ( dis[u] - C[j][1]) * C[j][0 ] ){
flag = true;
dis[v] = ( dis[u] - C[j][1]) * C[j][0];
}
}
if( !flag )
return false;
}
for( int j=0;j<tol;j++){
if( dis[ R[j][1] ] < ( dis[ R[j][0] ] - C[j][1] ) * C[j][0] )
return true;
}
return false;
}
int main(){
int n,m , s;
double v;
while( scanf(" %d %d %d %lf",&n,&m,&s,&v) !=EOF){
tol = 0;
int a,b;
double c,d,e,f;
while( m-- ){
scanf("%d%d%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
R[tol][0] = a;
R[tol][1] = b;
C[tol][0] = c;
C[tol][1] = d;
tol++;
R[tol][0] = b;
R[tol][1] = a;
C[tol][0] = e;
C[tol][1] = f;
tol++;
}
if( Bellman(s ,n,v) )
printf("YES\n");
else printf("NO\n");
}
return 0;
}
Travel Company
题意：让你来判断有无负环~是不是太典型了
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 205
int dis[maxn],cnt,n;
struct node{
int u,v,w;
}edge[1000000];
void add(int u,int v,int w){
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt++].w = w;
}
void Berman(){
memset(dis,inf,sizeof(dis));
int i,j;
for(int i=0;i<n-1;i++){
for(int j=0;j<cnt;j++){
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w)
{
dis[edge[j].v]=dis[edge[j].u]+edge[j].w;
}
}
}
for(int i=0;i<cnt;i++){
if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
{
printf("YES\n");
return ;
}
}
cout<<"NO"<<endl;
}
int main(){
int t,u,v,w,cost,m,num=0,p;
cin>>t;
while(t--){
num++;
cin>>n>>m>>p;
cnt= 0;
while(m--){
cin>>u>>v>>w>>cost;
add(u,v,cost*p-w);
}
printf("Case %d: ",num);
Berman();
}
return 0;
}
京公网安备 11010502036488号