此題大意為求從頂點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
崔佳星 閱讀(391)
評論(0) 編輯 收藏 引用 所屬分類:
xoj