#include <iostream>  
#include <queue>  
using namespace std;  
const long lmax = 1000000000;  
const long edge_maxn = 30005;  //边的最大上限  
const long point_maxn = 1500005;   //点的最大上限  
struct node  
{/*node存储边，一个edge代表一条边*/  
    int v;     //终点位置  
    int w;     //权值  
    int next;  //同一起点的下一条边存储在edge数组中的位置
}edge[edge_maxn];  
int pre[point_maxn];  //以该点为起点的第一条边存储在edge数组中的位置  
int n;  //点的数量  
int m;  //边的数量  
queue<int> Q;  
int dirs[point_maxn];  
bool vis[point_maxn];  
void Init()  
{  
    memset(pre,-1,sizeof(pre));  
    int Index = 1;  
    int i,j,flag;  
    int x,y,w;  
    for(i=0;i<m;i++)  
    {  
        scanf("%d%d%d",&x,&y,&w);  
        for(flag=0,j=pre[x];j!=-1;j=edge[j].next)  
        {//重边的情况  
            if(y == edge[j].v)  
            {  
                if(w < edge[j].w)  
                    edge[j].w = w;  
                flag = 1;  
                break;  
            }  
        }         
        if(flag == 1)  
            continue;  
        edge[Index].v = y;  
        edge[Index].w = w;  
        edge[Index].next = pre[x];  //保存x起点的上一条边在edge数组中的位置  
        pre[x] = Index++;  //位置更新  
    }  
}  
void print(int end)  
{  
    printf("%d\n",dirs[end]);  
}  
void SPFA()  
{  
    int start = 1;  
    int end = n;    
    while(!Q.empty())  
    {  
        Q.pop();  
    }  
    memset(vis,0,sizeof(vis));    //初始每个点的访问记录
    fill(dirs,dirs+point_maxn,lmax);  
      
    dirs[start] = 0;  
    vis[start] = 1;  
    Q.push(start);  
    while(!Q.empty())  
    {  
        int top = Q.front(); //边的起点  
        Q.pop();  
        vis[top] = 0;  
        for(int j=pre[top];j!=-1;j=edge[j].next)  
        {  
            int e = edge[j].v; //边的终点  
            if(dirs[e] > edge[j].w + dirs[top])  
            {  
                dirs[e] = edge[j].w + dirs[top];  
                if(!vis[e])  
                {  
                    Q.push(e);  
                    vis[e] = 1;  
                }  
            }  
        }  
    }  
    print(end);  
}  
int main()  
{  
    while(scanf("%d%d",&n,&m)!=EOF )  
    {  
        Init();  
        SPFA();  
    }  
    //system("pause");  
    return 0;  

• Re:spfa+临接链表wa掉了，跪求大牛开导啊帮我看看哪错了？ (2450) AllClear 2016-11-15 21:14:39