昂贵的聘礼 poj 1062 Dijkstra-白红宇

昂贵的聘礼 poj 1062 Dijkstra

阅读量：6858 次

发布时间：2019-06-26

本文共 2516 字，大约阅读时间需要 8 分钟。

中文题，题意就不多说了，讲讲思路吧，先根据题意构图，与普通最短路不同的是这一题加了一个Rank，每个点都有一个Rank，题目要求最短路径上的点的Rank的最大差值在

M范围内，Dijkstra判断条件时加上Rank约束就行了。我没有添加汇点直接写的，另贴上别人添加汇点的写法。

我的代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #pragma comment (linker,"/STACK:102400000,102400000")#define maxn 1005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6typedef long long ll;using namespace std;int mp[110][110];int visit[110],dist[110],selfcost[110],Rank[110];int M,N;int Dijkstra(int s,int e){ int i,j,now,mi; memset(visit,0,sizeof(visit)); memset(dist,INF,sizeof(dist)); for (i=1;i<=N;i++) if (Rank[i]>=s&&Rank[i]<=e) dist[i]=mp[1][i]; dist[1]=0; visit[1]=1; for (i=1;i<=N;i++) { now=-1; mi=INF; for (j=1;j<=N;j++) { if (Rank[j]>=s&&Rank[j]<=e&&!visit[j]&&dist[j]
               
                =s&&Rank[j]<=e&&!visit[j]&&mp[now][j]
                
                 dist[now]+mp[now][j]) dist[j]=dist[now]+mp[now][j]; } } int minn=INF; for (i=1;i<=N;i++) {// printf("%d\n",dist[i]); if (dist[i]+selfcost[i]

别人添加会点的代码：

http://www.cnblogs.com/yongze103/archive/2010/08/19/1803757.html

#include
    
     using namespace std;int M,N,dengji[110];int dis[110],map[110][110];bool vis[110];void dijkstra(int m,int n){    int i,k,num=1;    int min;    memset(vis,0,sizeof(vis));    memset(dis,127,sizeof(dis));    vis[0]=1;    for(i=0;i<=N;i++)        if( dengji[i]>=m && dengji[i]<=n)            dis[i]=map[0][i];        k=0;        while(1)        {            min=99999999;            for(i=0;i<=N;i++)                if(dengji[i]>=m && dengji[i]<=n && !vis[i] && min>dis[i])                {                    min=dis[i];                    k=i;                }                vis[k]=1;                if(k==1)                    return;            for(i=0;i<=N;i++)                if( dengji[i]>=m && dengji[i]<=n && !vis[i] && dis[i]>dis[k]+map[k][i])                {                    dis[i]=dis[k]+map[k][i];                }        }}int main(){    int i,j,k,t,p;    memset(map,127,sizeof(map));    cin>>M>>N;    int ans=999999999;    for(i=1;i<=N;i++)    {        scanf("%d%d%d",&map[0][i],&dengji[i],&k);        for(j=1;j<=k;j++)        {            scanf("%d%d",&t,&p);            map[t][i]=p;        }    }    for( i=dengji[1]-M; i<=dengji[1]; i++)    {        dijkstra(i,i+M);        if(ans>dis[1])            ans=dis[1];    }    cout<
     
      <

转载于:https://www.cnblogs.com/i8888/p/4044015.html

你可能感兴趣的文章

Kafka的生产者和消费者代码解析

查看>>

Intellij Idea编译项目下的.java文件时的编码问题

查看>>

【深度学习系列】PaddlePaddle可视化之VisualDL

查看>>

[离散时间信号处理学习笔记] 11. 连续时间信号的采样与重构

查看>>

python os.system()和os.popen()

查看>>