C--最短路

PRoblem Description

Input

Output

Example Input

3 11 2 31 2
Example Output
3
SPFA算法：
#include<stdio.h>#include<string.h>#include<stdlib.h>#define maxn 500005#define max 0x3f3f3f3fstruct node{    int v;    int w;    int next;}map[4000005];int queue[maxn];int dist[maxn];int book[maxn];int head[maxn];int front,rear,n,cnt;void add(int u,int v,int w){    map[cnt].v=v;    map[cnt].w=w;    map[cnt].next=head[u];    head[u]=cnt++;}void spfa(int s){    int i,u,v,w;    for(i=0;i<=n;i++)    {        book[i]=0;        dist[i]=max;    }    dist[s]=0;    book[s]=1;    rear=(rear+1)%maxn;    queue[rear]=s;    while(front!=rear)    {        front=(front+1)%maxn;        u=queue[front];        book[u]=0;        for(i=head[u];i!=-1;i=map[i].next)        {            v=map[i].v;            w=map[i].w;            if(dist[v]>dist[u]+w)            {                dist[v]=dist[u]+w;                if(!book[v])                {                    rear=(rear+1)%maxn;                    queue[rear]=v;                    book[v]=1;                }            }        }    }}int main(){    int i,m,u,v,w,s,e;    while(scanf("%d%d",&n,&m)!=EOF)    {        front=rear=cnt=0;        memset(head,-1,sizeof(head));        while(m--)        {            scanf("%d%d%d",&u,&v,&w);            add(u,v,w);            add(v,u,w);        }        scanf("%d%d",&s,&e);        spfa(s);        printf("%d/n",dist[e]);    }    return 0;}