27/7/2012 ICPC培训(一)

眨眼培训就过了大半喽。我还是很喜欢的。。。
上午做了HDU2112
还是求最短路径的，不同的是这题没有直接给地点标号，需要我们来处理。
这题要注意一下集中情况：
1、start、end地点在下面的路径中不一点会出现，所以在标号时需要对这两个点也处理。
2、无向图的处理可能会增加时间复杂度，但不会改变最短路径的长度，因为除非是负权边，
否则a->b被处理过，b->a一点不会被处理了。
3、这题的建图。利用temp[][]表将地点不重复地存储起来，建立地点和数字标号间的唯一对应
关系。然后在查找建图。
4、SPFA算法，不仅仅可以求出最短路径，还可以判断两点是否连通。（有向图、无向图均可）
代码：
[cpp]
#include
#include
#include
using namespace std;

const int maxRoad=10001; //路径数
const int maxSize=151; //地点数
const int maxLen=31; //地点的最大长度
const int INF=0x7fffffff;

struct node //边
{
char start[maxLen];
char end[maxLen];
int from;
int to;
int cost;
}edge[maxRoad];

int minPath[maxSize]; //最短路
bool inQ[maxSize]; //是否在队列中
int numEdge,numAdress,from,to; //路径数、点数、起点、终点
char start[maxLen],end[maxLen];
char temp[maxSize][maxLen]; //不重复存放地存放每个点
vector myV[maxSize]; //连接表

int findIndex(char c[]) //找地点的标示
{
for(int i=0;i {
if(strcmp(c,temp[i])==0)
{
return i;
}
}

return -1;
}

void input()
{
numAdress=0;
getchar();
scanf("%s%s",&start,&end);

//如果不在temp[][]表中就放进去
if(findIndex(start)==-1) strcpy(temp[numAdress++],start);
if(findIndex(end)==-1) strcpy(temp[numAdress++],end);

for(int i=0;i {
getchar();
scanf("%s%s%d",&edge[i].start,&edge[i].end,&edge[i].cost);

if(findIndex(edge[i].start)==-1) strcpy(temp[numAdress++],edge[i].start);
if(findIndex(edge[i].end)==-1) strcpy(temp[numAdress++],edge[i].end);
}
}

void buildMap()
{
for(int j=0;j {
myV[j].clear();
}