poj2449 Remmarguts' Date K短路 A*

K短路裸题。
#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

struct Edge{

    int too, nxt, val;

}edge[100005];

struct Odge{

    int too, nxt, val;

}odge[100005];

struct Node{

    int idd, hfc, gfc;

    bool operator<(const Node &x)const{

        return hfc+gfc>x.hfc+x.gfc;

    }

}d[1000005];//n*k

int n, m, s, t, k, uu, vv, ww, hea[1005], oea[1005], cnt, ont, dis[1005];

int din, tms[1005], ans;

bool vis[1005];

void add_edge(int fro, int too, int val){

    edge[++cnt].nxt = hea[fro];

    edge[cnt].too = too;

    edge[cnt].val = val;

    hea[fro] = cnt;

}

void add_odge(int fro, int too, int val){

    odge[++ont].nxt = oea[fro];

    odge[ont].too = too;

    odge[ont].val = val;

    oea[fro] = ont;

}

void dijkstra(){

    memset(dis, 0x3f, sizeof(dis));

    dis[t] = 0;

    for(int i=1; i<=n; i++){

        int mini=0;

        for(int j=1; j<=n; j++)

            if(!vis[j] && dis[mini]>dis[j])

                mini = j;

        vis[mini] = true;

        if(!mini)   return ;

        for(int i=oea[mini]; i; i=odge[i].nxt){

            int v=odge[i].too;

            dis[v] = min(dis[v], odge[i].val+dis[mini]);

        }

    }

}

void aStar(){

    d[++din] = (Node){s, 0, 0};

    while(din){

        Node j=d[1];

        pop_heap(d+1, d+1+din);

        din--;

        tms[j.idd]++;

        if(j.idd==t && tms[t]==k){

            printf("%d\n", j.hfc+j.gfc);

			return ;

        }

        if(tms[j.idd]>k)    continue;

        for(int i=hea[j.idd]; i; i=edge[i].nxt)

			if(tms[edge[i].too]<=k){

    	        d[++din] = (Node){edge[i].too, j.hfc+edge[i].val, dis[edge[i].too]};

        	    push_heap(d+1, d+1+din);

        	}

    }

	cout<<"-1\n";

}

int main(){

    cin>>n>>m;

    for(int i=1; i<=m; i++){

        scanf("%d %d %d", &uu, &vv, &ww);

        add_edge(uu, vv, ww);

        add_odge(vv, uu, ww);

    }

	cin>>s>>t>>k;

	if(s==t)	k++;

    dijkstra();

    aStar();

    return 0;

}
巴特西

poj2449 Remmarguts' Date K短路 A*

最新文章

热门文章
