2018南京网络赛l题 magical girl haze（分层图 优先队列优化的dijkstra） -凯发ag旗舰厅登录网址下载

使用优先队列优化过的dijkstra时间复杂度可以达到o（v*logn），还是很快的。

#include                 //最好是用long long 类型的。 
#include
#include  
using namespace std;
typedef long long ll;
const int maxe=2e5 7;
const int maxv=1e5 7;
int n,m,k,con=0;
ll dis[maxv*12 7];
ll head[maxv*12 7];
int vis[maxv*12 7];
struct node                        //以边为重点。 
{
    int u,v,value,next;
    node (int u=0,int v=0,int value=0,int next=0):u(u),v(v),value(value),next(next){}
}e[2*maxe*12 7];         
struct node 
{
    int id;
    ll value;
    node(int id,ll value):id(id),value(value){}  //结构体是和普通的数据差不多。直接写上就能用吧。 
    bool operator < (const node &a)const                   //优先队列按照从小到大的顺序输出。 
    {
        return value>a.value ;    
    }    
}; 

void addedge(int u,int v,int value)  //唯有结构体数组才可以进行模拟链表。 
{
    e[con]=node(u,v,value,head[u]);
    head[u]=con ;
}
void dig()
{
    priority_queue< node >q;
    q.push( node(1,0));
    dis[1]=0;
    vis[1]=1;
    node temp(0,0) ;                         //之后进行验证结构体和类之间的关系。 
    while(!q.empty())
    {
        temp=q.top();
        q.pop();
        int u=temp.id ;
        vis[u]=1;
        for(int i=head[u];~i;i=e[i].next )   //但是到下一个点的距离确是可以进行优化的。 
        { 
            ll v=e[i].v ;
            if( vis[ v ]==1 )continue;
            if( temp.value   e[i].value             {
                dis[ v ]= temp.value   e[i].value ;        //最为重要的入队没有考虑啊。 
                 q.push( node( v,dis[v] ) );
            }    
        }
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        con=0;                    //一定不要忘了进行初始化的啊。这里是很重要的。 
        memset(head,-1,sizeof(head));
        memset(dis,125,sizeof(dis));
        memset(vis,0,sizeof(vis));
        scanf("%d %d %d",&n,&m,&k);
        int u,v,value;
        for(int i=0;i         {
            scanf("%d %d %d",&u,&v,&value); 
            for(int j=0;j<=k;j )
            {
                addedge( u n*j,v n*j,value );    
                if(j!=k)
                    addedge(u n*j,v n*(j 1),0);    //建立层与层之间的关联。 
            }    
        }
        dig();
        ll ans=9042521604759584125;
        for(int i=0;i<=k;i )
            if(dis[n n*i]                 ans=dis[n n*i];
        printf("%lld\n",ans);    
    }     
    return 0;    
} 

总结

以上是凯发ag旗舰厅登录网址下载为你收集整理的2018南京网络赛l题 magical girl haze（分层图 优先队列优化的dijkstra）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发ag旗舰厅登录网址下载网站内容还不错，欢迎将凯发ag旗舰厅登录网址下载推荐给好友。