此题大意为求从顶点1到顶点n的最短路径。
所以采用最短路径的算法。
想省事的话,可以使用弗洛伊德,但是n的值为10^5,这样肯定超时。
所以本题采用SPFA算法。见下面代码
#include<stdio.h>
#include<malloc.h>
#include<queue>
#include<string.h>
using namespace std;
typedef struct node
{
int id;
int distance;
struct node *next;
}Node,*LNode;
int n,m;
LNode array[100010];//邻接链表
int in_queue[100010];//记录一个点是否在队列中
int between_distance[100010];//记录起始点到两个点之间的距离
queue<int> q;//建立一个队列
void init_array()
{
for(int i = 0;i <= n;++i)
{
array[i] = (LNode)malloc(sizeof(Node));
array[i]->id = i;
array[i]->distance = 0;
array[i]->next = NULL;
}
}
void insert_node(LNode header,LNode &insert_node)
{
while(header->next != NULL)
header = header->next;
insert_node->next = header->next;
header->next = insert_node;
}
//任何两点之间的距离设置为-1,表示正无穷
void init_distance()
{
for(int i = 0;i <= n;++i)
{
between_distance[i] = -1;
}
//第一个结点到自身为0
between_distance[1] = 0;
}
//松弛
void relax(int index)
{
if(between_distance[index] == -1)
return ;
LNode header = array[index]->next;
while(header != NULL)
{
if(between_distance[header->id] > between_distance[index] + header->distance || between_distance[header->id] == -1)
{
between_distance[header->id] = between_distance[index] + header->distance;
if(!in_queue[header->id])
{
q.push(header->id);
in_queue[header->id] = 1;
}
}
header = header->next;
}
}
void SPFA()
{
//第一个点入队列
q.push(1);
in_queue[1] = 1;
int index = 0;
while(!q.empty())
{
index = q.front();
q.pop();
in_queue[index] = 0;
relax(index);
}
}
int main()
{
int x,y,distance;
scanf("%d%d",&n,&m);
init_array();
for(int i = 0;i < m;++i)
{
scanf("%d%d%d",&x,&y,&distance);
LNode node = (LNode)malloc(sizeof(Node));
node->id = y;
node->distance = distance;
insert_node(array[x],node);
node = (LNode)malloc(sizeof(Node));
node->id = x;
node->distance = distance;
insert_node(array[y],node);
}
init_distance();
memset(in_queue,0,sizeof(in_queue));
SPFA();
if(between_distance[n] == -1)
{
printf("-1\n");
}
else
printf("%d\n",between_distance[n]);
return 0;
}
posted on 2012-04-06 19:59
崔佳星 阅读(360)
评论(0) 编辑 收藏 引用 所属分类:
xoj