最短路合集

1.条件类型最短路

https://ac.nowcoder.com/acm/contest/370/B

题意：n个点，m无向边，n个点有一部分是特殊的点，求从1走到n最短路是多少。并且该最短路满足走过的特殊点不超过K.
分析: 将所有点的状态分离成K个点(K分层图)，表示到当前该点的走过的特殊点有 $图片说明$ 个。然后跑一遍dij即可。(dis多建一维条件跑dij也可以)

#include<bits/stdc++.h>
#define ll long long
#define inf 0x7f7f7f7f
#define pr pair<ll,ll>

using namespace std;

const int N=4e6+10;

struct node{
    int v,len,next;
}a[N*2];
int pre[N],cnt=0;
ll dis[N],vis[N];

void add( int u,int v,int len )
{
//    a[cnt].v=v , a[cnt].len=len , a[cnt].next=pre[u];
    a[cnt]={ v,len,pre[u] };
    pre[u]=cnt++;
}

void init()
{
    memset(pre,-1,sizeof(pre)),cnt=0;
}

void dijstra( int s ) // 起点 
{ 
    memset( dis,inf,sizeof(dis) );
    memset( vis,0,sizeof(vis) );
    priority_queue<pr,vector<pr>,greater<pr> > q;
    q.push( make_pair(0,s) );
    dis[s]=0;
    while( q.size() ) 
    {
        int u=q.top().second;
        q.pop();
        vis[u]=1;
        for( int i=pre[u];~i;i=a[i].next )
        {
            int v=a[i].v,len=a[i].len;
            if( !vis[v] && dis[v]>dis[u]+len )
            {
                dis[v]=dis[u]+len;
                q.push( make_pair(dis[v],v) );
            }
        } 
    }
}

int tag[N];

int main()
{
    init();
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for( int i=1;i<=n;i++ ) scanf("%d",&tag[i]);
    if( tag[1] ) k--;
    if( tag[n] ) k++;

    for( int i=1;i<=m;i++ )
    {
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        for( int j=0;j<=k;j++ )
        {
            if( !tag[b] ) add(a+n*j,b+n*j,c);
            if( !tag[a] ) add(b+n*j,a+n*j,c);
        }
        for( int j=0;j<k;j++ )
        {
            if( tag[b] ) add(a+n*j,b+n*j+n,c);
            if( tag[a] ) add(b+n*j,a+n*j+n,c);
        }
    }
    ll ans=inf;
    dijstra(1);
    for( int i=1;i<=k+1;i++ )    ans=min(ans,dis[i*n]);


    if( ans!=inf ) printf("%lld\n",ans);
    else puts("-1");
}

2.最短路K次免费(半价都一样)

#include<bits/stdc++.h>
#include<queue>
#define int long long
#define INF 1e18
using namespace std;

inline int read()
{
    int f=1,w=0;char s=getchar();
    for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
    for( ;isdigit(s);w=w*10+s-48,s=getchar());
    return w*f;
}

int dis[200010][60],n,m,p,head[200010],cnt;

// head[i] 路线起始位置索引到 可能到的位置  结合 edge[i]索引
// dis[i][j] i表示到位置i  j表示打折次数 dis[i][j]表示最小花费

struct Edge{
    int from,to,next,dis;
}edge[1000010];

inline void addedge( int u,int v,int w ) // 存有向网
{
    cnt++;
    edge[cnt].from=u;
    edge[cnt].to=v;
    edge[cnt].dis=w;
    edge[cnt].next=head[u];
    head[u]=cnt;     
}
struct node{
    int num,dis,tim;
    friend bool operator < (node a,node b) //优先级
    {
        return a.dis>b.dis;
    }
};

priority_queue<node> q;  //  优先队列

inline void dij(int s)
{
    int u,v,w,i,j,k,tim;
    dis[s][0]=0;
    q.push( (node){s,0,0} );
    while( !q.empty() )
    {
        node front=q.top();
        q.pop();
        u=front.num;  // u表示到位置
        tim=front.tim;  // tim 表示打折次数
        if(tim>p) continue;
        if( front.dis>dis[u][tim] ) continue;
        for(i=head[u];i;i=edge[i].next ) //  有点bfs的意思
        {
            v=edge[i].to;
            w=edge[i].dis;
            if( dis[v][tim]>dis[u][tim]+w )
            {
                dis[v][tim]=dis[u][tim]+w;
                q.push( (node) {v,dis[v][tim],tim} );
            }
            if( dis[v][tim+1]>dis[u][tim]+edge[i].dis/2 )
            {
                dis[v][tim+1]=dis[u][tim]+edge[i].dis/2;
                q.push( (node) {v,dis[v][tim+1],tim+1} );
            }
        }
    }
    return;
}
signed main(){
    n=read();m=read();p=read();
    int i,j,k,st,ed;st=1;ed=n;
    for( i=1;i<=m;i++ )
    {
        int x,y,z;
        x=read();y=read();z=read();
        addedge(x,y,z);
    }

////  调试
//    cout<<endl;
//    for( int i=1;i<=n;i++ )
//    {
// //       printf("%d ",head[i]);
//      for(j=head[i];j;j=edge[j].next )
//      {
//          printf("%d ",j);
//      }cout<<endl;
//    }cout<<endl;
//   

    for( int i=0;i<=200000;i++ )  // 初始化操作
    {
        for( int j=0;j<=10;j++ )
        {
            dis[i][j]=INF;
        }
    }
    dij(st);
    int ans=INF;
    for( int i=0;i<=p;i++ )
    {
        ans=min( ans,dis[n][i] );
    }
    if( ans==INF ) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

HDU6797
3.n阶完全图，每条边都有一个边权，你可以去掉k条边，使得最短路的长度尽量长。求最短路最长是多少。
暴力修改最短路上的边，然后跑最短路，迭代k次。答案去最大。

最短路合集

全站热榜