最短路问题，有Bellman-Ford，SPFA，Dijkstra，Floyd这几种算法，我最先学Bellman-Ford，但在学了SPFA和Dijkstra只好几乎没用过它了，效率比较差，图论的题最短路算做得比较多的，这里就选几道代表题来复习吧。
第一道：智捅马蜂窝
典型的最短路，首先按照题意把图建好，然后一次Dijkstra就行了，不过我习惯写priority_queue，据说在考试写有风险（NOIP的话）？知道的留个言啊，这个言论让我后面都手写堆了。近乎裸题，不多说了。
代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn = 100 + 10;
const int inf = 0x7fffffff;
int n;
int v;
double x[maxn],y[maxn];
bool flag[maxn][maxn];
bool done[maxn];
double path[maxn][maxn],dist[maxn];
void init()
{
freopen("hornet.in","r",stdin);
freopen("hornet.out","w",stdout);
}
double cal(int i,int j)
{
double com,com2;
if(!flag[i][j])
{
return inf;
}
com = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
com2 = com/v;
return com2;
}
void create_map()
{
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
{
if(i == j)
{
path[i][j] = 0;
}
else
{
path[i][j] = cal(i,j);
}
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
{
if(x[i] == x[j] && y[i] < y[j])
{
flag[j][i] = true;
path[j][i] = sqrt(2*(y[j] - y[i]) / 10.00);
}
}
}
void readdata()
{
memset(flag,false,sizeof(flag));
memset(done,false,sizeof(done));
memset(path,-1,sizeof(path));
scanf("%d%d",&n,&v);
for(int i = 1;i <= n;i++)
{
int t;
scanf("%lf%lf",&x[i],&y[i]);
scanf("%d",&t);
if(t!=0)flag[t][i] = flag[i][t] = true;
}
create_map();
}
void predoing()
{
for(int i = 1;i <= n;i++)
dist[i] = 1e30;
}
void solve()
{
typedef pair<double,int>pii;
priority_queue<pii,vector<pii>,greater<pii> >q;
predoing();
dist[1] = 0;
q.push(make_pair(dist[1],1));
while(!q.empty())
{
pii u = q.top();q.pop();
if(done[u.second])continue;
int k = u.second;
double min = dist[k];
done[k] = true;
for(int i = 1;i <= n;i++)
{
if(!flag[k][i])continue;
if(done[i])continue;
if(min + path[k][i] < dist[i])
{
dist[i] = min + path[k][i];
q.push(make_pair(dist[i],i));
}
}
}
printf("%.2lf",dist[n]);
}
int main()
{
init();
readdata();
solve();
return 0;
}
第二道：微子危机——战略
是最短路的一个变种，就是确定了起点但没确定终点的最短路，最开始做的时候还没看出来。方法就是从起点开始每到达一个点就累加ans，所有点都到达之后就求出了所求的ans了，知道了方法之后也算一道简单的题吧，不过在这道题中我手写了堆，还用了构造函数。没有用STL，所以有点冗长，凑合着看吧。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 10000 + 10;
const int maxm = 500000 + 10;
struct tnode
{
int d,w;
tnode(){};
tnode(int w,int d):w(w),d(d){};
}node[maxn];
struct pnode
{
int dian,quan;pnode *next;pnode(){}
pnode(int dian,int quan,pnode* next):dian(dian),quan(quan),next(next){}
}*first[maxn],__[maxm << 1],*tot = __;
tnode heap[maxm];
int dist[maxn];
bool done[maxn];
int n,m,l;
int size = 0;
void init()
{
freopen("tyvj1221.in","r",stdin);
freopen("tyvj1221.out","w",stdout);
}
void readdata()
{
scanf("%d%d%d",&n,&m,&l);
for(int i = 1;i <= l;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
first[x] = new(tot++)pnode(y,z,first[x]);
first[y] = new(tot++)pnode(x,z,first[y]);
}
}
void del()
{
heap[1] = heap[size--];
int i = 1;
int j = i << 1;
if(j < size && heap[j].w > heap[j+1].w)++j;
while(j <= size && heap[i].w > heap[j].w)
{
swap(heap[i],heap[j]);
i = j;
j = j << 1;
if(j < size && heap[j].w > heap[j+1].w)++j;
}
}
void add(tnode x)
{
heap[++size] = x;
int i = size;
int j = i >> 1;
while(i > 1 && heap[i].w < heap[j].w)
{
swap(heap[i],heap[j]);
i = j;
j = i >> 1;
}
}
void solve()
{
int ans = 0;int count = 0;
for(int i = 1;i <= n;i++)dist[i] = inf;
memset(done,false,sizeof(done));
dist[m] = 0;
add(tnode(dist[m],m));
while(size)
{
tnode u = heap[1];del();
if(done[u.d])continue;
int k = u.d;
int min = u.w;
done[k] = true;
ans += min;
++count;
for(pnode *p = first[k];p != NULL;p = p->next)
{
if(done[p->dian])continue;
if(min + p->quan < dist[p->dian])
{
dist[p->dian] = min + p->quan;
add(tnode(dist[p->dian],p->dian));
}
}
}
if(count == n)
{
printf("%d M(s) are needed.",ans);
}
else
printf("Sth wrong.");
}
int main()
{
init();
readdata();
solve();
return 0;
}
第三题：心灵的抚慰
一道最小环问题。做那么些题就遇到了这一道。思想就是在做Floyd的时候顺便把最小环求出来，也近乎裸题，不知道在不在NOIP范围，感兴趣的见：最小环
还记得当时对着这道题一筹莫展的时候，一问神牛，10分钟不到就把代码打了出来，然后A了。。。当时那个自惭形秽啊~不说了、
代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x7f7f7f7f;
const int maxn=250+10;
int n,m,ans;
int map[maxn][maxn];
int f[maxn][maxn];
void init()
{
freopen("rqnoj389.in","r",stdin);
freopen("rqnoj389.out","w",stdout);
}
void readdata()
{
int a,b,c;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
map[i][j]=map[j][i]=inf >> 2;
f[i][j]=f[j][i]=inf >> 2;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]=map[b][a]=c;
f[a][b]=f[b][a]=c;
}
}
int min(int a,int b)
{
return a<b?a:b;
}
void solve()
{
ans=inf >> 2;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
for(int j=i+1;j<k;j++)
{
ans=min(ans,map[i][j]+f[k][i]+f[j][k]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(k==i || k==j || i==j)continue;
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
}
}
if (ans==inf >> 2)
printf("He will never come back.");
else
printf("%d",ans);
}
int main()
{
init();
readdata();
solve();
return 0;
}
总结：这些题肯定不能代表所有类型的题(NOIP)，但是我一直抱着Dijkstra+heap走天下的思想，其他类型的题也就做得少了。其实图论的难点就在建图了，只要能抽象出模型，打代码应该是比较简单的事情了。