[USACO06NOV] Roadblocks

严格次短路

A* 算法求第二短

#include<queue>
#include<cstdio>
#include<cstring>
#define N 5001
#define M 200001
using namespace std;
int n,s,t;
int dis1[N];
bool vis[N];
int front[N],to[M],nxt[M],val[M],tot;
struct node
{
    int num,dis;
    bool operator < (node p) const
    {
        return dis+dis1[num]>p.dis+dis1[p.num];
    } 
}now,nt;
void add(int u,int v,int w)
{
    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=w;
}
void init()
{
    int m,u,v,w;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
}
void spfa()
{
    memset(dis1,63,sizeof(dis1));
    queue<int>q;
    dis1[n]=0;
    vis[n]=true;
    q.push(n);
    int now;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        vis[now]=false;
        for(int i=front[now];i;i=nxt[i])
            if(dis1[to[i]]>dis1[now]+val[i])
            {
                dis1[to[i]]=dis1[now]+val[i];
                if(!vis[to[i]])
                {
                    q.push(to[i]);
                    vis[to[i]]=true;
                }
            }
    }
}
void Astar()
{
    if(dis1[1]>1e9) 
    {
        printf("-1");
        return;
    }    
    int cnt=0,last=-1;
    priority_queue<node>q;
    now.num=1;
    now.dis=0;
    q.push(now);
    while(!q.empty())
    {
        now=q.top();
        q.pop();
        if(now.num==n) 
        {
            cnt++;
            if(cnt>1 && now.dis!=last) 
            {
                printf("%d",now.dis);
                return;
            }
            else last=now.dis;
        }
        for(int i=front[now.num];i;i=nxt[i])
        {
            nt.num=to[i];
            nt.dis=now.dis+val[i];
            q.push(nt);
        }
    }
    printf("-1");
}
int main()
{
    init();
    spfa();
    Astar();
}

[USACO06NOV] Roadblocks

标签：nat   name   ted   astar   any   scan   art   href   lin