最短路题目整理 Hdu 2066 + 1839 + LightOJ 1099（次短路）

￡神魔★判官ぃ 2021-12-05 03:32 218阅读 0赞

**Hdu 2066 一个人的旅行**

思路：新增一个源点和一个汇点，将所有起点与源点连接权值为0的边，将所有终点与汇点连接权值为0的边，从源点到汇点求最短路。

#include <cstdio>
    #include <cstring> 
    #include <algorithm> 
    #include <queue>
    using namespace std;
    
    const int INF = 0x5fffffff;  //权值上限
    const int MAXPT = 1010;       //顶点数上限
    const int MAXEG = 200002;     //边数上限
    
    //点存储1~n
    class Dijkstra     /*邻接表 + 优先队列 + Dijkstra求最短路*/
    {
    private:
    	int n,e;
        int dis[MAXPT], head[MAXPT];
        int visit[MAXPT];
    
        struct Node
    	{
    		int v,dis;
            Node () {}
    		Node (int _v,int _dis)
    		{
    			v=_v;
    			dis=_dis;
    		}
    		bool operator < (const Node a) const
    		{
    			return dis>a.dis;
    		}
    	};
    	
    	struct Edge
    	{
    		int v, w, next;
    		Edge () {}
    		Edge (int _v, int _next, int _w)
    		{
    			v=_v;
    			next=_next;
    			w=_w;
    		}
        }edges[MAXEG];
    
    public:
        inline void init (int vx)
    	{ 
            n = vx;
    		e = 0; 
            memset(head,-1,sizeof(int) * (vx + 1));
        } 
      
        inline void Add (int u, int v, int w)
    	{ 
            edges[e] = Edge(v, head[u], w);
            head[u] = e++;
        } 
      
        void print ()
    	{ 
            for (int i=1;i<=n;i++)
    		{ 
                printf("%d: ", i); 
                for (int j=head[i]; j!=-1; j=edges[j].next)
                    printf(" %d", edges[j].v);
    			printf("\n");
            } 
        } 
      
        int dijkstra (int src, int des)
    	{ 
            Node first, next;
            priority_queue <Node> Q;
            for (int i=0;i<=n;i++)
    		{ 
                dis[i] = INF; 
                visit[i] = false; 
            } 
      
            dis[src]=0; 
            Q.push (Node(src, 0));
      
            while (!Q.empty())
    		{ 
                first = Q.top(); 
                Q.pop(); 
                visit[first.v] = true;
      
                for (int i=head[first.v] ; i!=-1 ; i=edges[i].next)
    			{ 
                    if (visit[edges[i].v])
    					continue; 
                    next = Node(edges[i].v, first.dis + edges[i].w);
                    if (next.dis < dis[next.v])
    				{ 
                        dis[next.v] = next.dis; 
                        Q.push(next); 
                    } 
                } 
            }
            return dis[des]; 
        }
    }ob; 
      
    int main ()
    {
    	int t,s,d;
        while (~scanf("%d%d%d",&t,&s,&d))
    	{
    		int i=0,k;
    		ob.init(1005);
    		for (i=1;i<=t;i++)
    		{
    			int u,v,w;
    			scanf("%d%d%d",&u,&v,&w);
    			u++;
    			v++;
    			ob.Add(u,v,w);
    			ob.Add(v,u,w);
    			
            }
    		
    		for (i=1;i<=s;i++)
    		{
    			scanf("%d",&k);
    			k++;
    			ob.Add(1,k,0);
    			ob.Add(k,1,0);
    		}
    		int end=1002;
    		for (i=1;i<=d;i++)
    		{
    			scanf("%d",&k);
    			k++;
    			ob.Add(k,end,0);
    			ob.Add(end,k,0);
    		}
    		printf("%d\n",ob.dijkstra(1,end));
    	}
    	return 0; 
    }

**Hdu 1839 Delay Constrained Maximum Capacity Path**

题意：有N个点，点1为珍贵矿物的采矿区， 点N为加工厂，有M条双向连通的边连接这些点。走每条边的运输容量为C，运送时间为D。

他们要选择一条从1到N的路径运输， 这条路径的运输总时间要在T之内，在这个前提之下，要让这条路径的运输容量尽可能地大。

一条路径的运输容量取决与这条路径中的运输容量最小的那条边。

思路：因为每条路径的容量取决于这条路径中所有边中的最小容量，所以我们可以以此枚举最小容量。

如果最低容量越大，那么符合要求的路径就越少，所以，根据容量的大小，路径数量是单调的，所以可以二分

#include <cstdio>
    #include <cstring> 
    #include <algorithm> 
    #include <queue>
    using namespace std;
    
    const int INF = 0x3fffffff;  //权值上限
    const int MAXPT = 10002;       //顶点数上限
    const int MAXEG = 50002*2;     //边数上限
    
    int n,m,t;
    
    
    //点存储1~n
    class Dijkstra     /*邻接表 + 优先队列 + Dijkstra求最短路*/
    {
    private:
    	int n,e;
        int dis[MAXPT], head[MAXPT];
        int visit[MAXPT];
    
        struct Node
    	{
    		int v,dis;
            Node () {}
    		Node (int _v,int _dis)
    		{
    			v=_v;
    			dis=_dis;
    		}
    		bool operator < (const Node a) const
    		{
    			return dis>a.dis;
    		}
    	};
    	
    	struct Edge
    	{
    		int v, w, c,next;
    		Edge () {}
    		Edge (int _v, int _next,int _c, int _w)
    		{
    			v=_v;
    			next=_next;
    			c=_c;
    			w=_w;
    		}
        }edges[MAXEG];
    
    public:
        inline void init (int vx)
    	{ 
            n = vx;
    		e = 0; 
            memset(head,-1,sizeof(int) * (vx + 1));
        } 
      
        inline void Add (int u, int v, int c,int w)
    	{ 
            edges[e] = Edge(v, head[u],c, w);
            head[u] = e++;
        } 
      
        void print ()
    	{ 
            for (int i=1;i<=n;i++)
    		{ 
                printf("%d: ", i); 
                for (int j=head[i]; j!=-1; j=edges[j].next)
                    printf(" %d", edges[j].v);
    			printf("\n");
            } 
        } 
      
        int dijkstra (int src, int des,__int64 limit)
    	{ 
            Node first, next;
            priority_queue <Node> Q;
            for (int i=0;i<=n;i++)
    		{ 
                dis[i] = INF; 
                visit[i] = false; 
            } 
      
            dis[src]=0; 
            Q.push (Node(src, 0));
      
            while (!Q.empty())
    		{ 
                first = Q.top(); 
                Q.pop(); 
                visit[first.v] = true;
      
                for (int i=head[first.v] ; i!=-1 ; i=edges[i].next)
    			{
    				if (edges[i].c<limit)
    					continue;
                    if (visit[edges[i].v])
    					continue; 
                    next = Node(edges[i].v, first.dis + edges[i].w);
                    if (next.dis < dis[next.v])
    				{ 
                        dis[next.v] = next.dis; 
                        Q.push(next); 
                    } 
                } 
            }
            return dis[des]; 
        }
    }ob; 
      
    int main ()
    {
        int T;
        scanf("%d",&T);
        for (int Cas=1;Cas<=T;Cas++)
        {
    		scanf("%d%d%d",&n,&m,&t);
    		ob.init(n);
    		while (m--)
    		{
    			int u,v,c,w;
    			scanf("%d%d%d%d",&u,&v,&c,&w);
    			ob.Add(u,v,c,w);
    			ob.Add(v,u,c,w);
            }
    		__int64 left=0,right=2000000001,mid;
    		int temp;
    		while (left<=right)
    		{
    			mid=(left+right)>>1;
    			temp=ob.dijkstra(1,n,mid);
    			if (temp==t)
    				break;
    			if (temp>=t)
    				right=mid-1;
    			else
    				left=mid+1;
    		}
    			printf("%I64d\n",right);	
    	}
    	return 0; 
    }

**LightOJ 1099 Not the Best**

题目链接：[http://lightoj.com/volume\_showproblem.php?problem=1099][http_lightoj.com_volume_showproblem.php_problem_1099]

题意：每条边可以反复走，求次短路。

思路：A\*变形，改变启发式搜索时的退出条件即可，详见代码注释部分。

另一个实现：http://blog.csdn.net/airarts\_/article/details/7600426

#include <cstdio>
    #include <cstring> 
    #include <algorithm> 
    #include <queue>
    using namespace std;
    
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    
    const int INF = 0x3fffffff;  //权值上限
    const int MAXPT = 5010;       //顶点数上限
    const int MAXEG = 100000*2+200;     //边数上限
    
    //点存储1~n
    class Dijkstra     /*邻接表 + 优先队列 + Dijkstra求最短路*/
    {
    private:
    	int n,e,e1;
        int dis[MAXPT],head[2][MAXPT];
        int visit[MAXPT];
    	int cnt[MAXPT];   //启发式搜索标记
    
        struct Node
    	{
    		int v,dis,h;
            Node () {}
    		Node (int _v,int _dis,int _h)
    		{
    			v=_v;
    			dis=_dis;
    			h=_h;
    		}
    		bool operator < (const Node a) const
    		{
    			return dis+h>a.dis+a.h;
    		}
    	};
    	
    	struct Edge
    	{
    		int v, w, next;
    		Edge () {}
    		Edge (int _v, int _next, int _w)
    		{
    			v=_v;
    			next=_next;
    			w=_w;
    		}
        }edges[2][MAXEG];  //0存储原图,1存储反图
    
    public:
        inline void init (int vx)
    	{
            n = vx;
    		e = 0,e1=0; 
            memset(head[0],-1,sizeof(int) * (vx + 1));
    		memset(head[1],-1,sizeof(int) * (vx + 1));
        } 
    
        inline void Add (int u, int v, int w)
    	{ 
            edges[0][e] = Edge(v, head[0][u], w);
            head[0][u] = e++;
        } 
    
    	inline void Add1 (int u, int v, int w)
    	{ 
            edges[1][e1] = Edge(v, head[1][u], w);
            head[1][u] = e1++;
        } 
      
        int dijkstra (int src,int end)
    	{ 
            Node first, next;
            priority_queue <Node> Q;
            for (int i=0;i<=n;i++)
    		{ 
                dis[i] = INF; 
                visit[i] = false;
            } 
      
            dis[src]=0; 
            Q.push (Node(src, 0,0));
      
            while (!Q.empty())
    		{ 
                first = Q.top(); 
                Q.pop(); 
                visit[first.v] = true;
      
                for (int i=head[1][first.v] ; i!=-1 ; i=edges[1][i].next)
    			{ 
                    if (visit[edges[1][i].v])
    					continue; 
                    next = Node(edges[1][i].v, first.dis + edges[1][i].w,0);
                    if (next.dis < dis[next.v])
    				{ 
                        dis[next.v] = next.dis; 
                        Q.push(next); 
                    }
                }
            }
    		return dis[end];
        }
    
    	int Astar_Kth (int src,int end,int K)
    	{
    		Node first, next;
            priority_queue <Node> Q;
    		memset (cnt,0,sizeof(cnt));
    		if (dis[src]==INF) return -1;
    		if (src==end) K++; //注意当s==t时需要计算K+1短路,因为s到t这条距离为0的路不能算在这K短路中,这时只需将K++
    
    		Q.push (Node(src,0,dis[src]));
    
            while (!Q.empty())
    		{ 
                first = Q.top();
                Q.pop();
                cnt[first.v]++;
    			if (cnt[first.v]>K) continue;
    //			if (cnt[end]==K) return first.dis;
    			if (first.dis+first.h>dis[src])
    			{
    //				printf("%d %d %d~~\n",first.dis,first.h,dis[src]);
    				return first.dis+first.h;
    			}
                for (int i=head[0][first.v] ; i!=-1 ; i=edges[0][i].next)
    				Q.push(Node(edges[0][i].v,first.dis+edges[0][i].w,dis[edges[0][i].v]));
    		}
    		return -1;
    	}
    }ob; 
    
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,n,m;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d%d",&n,&m);
    		ob.init(n);
    		while (m--)
    		{
    			int u,v,w;
    			scanf("%d%d%d",&u,&v,&w);
    			ob.Add(u,v,w);
    			ob.Add(v,u,w);
    			ob.Add1(v,u,w);
    			ob.Add1(u,v,w);
            }
    		ob.dijkstra(n,1);
    		printf("Case %d: %d\n",Cas,ob.Astar_Kth(1,n,2));
    	}
    	return 0; 
    }

[http_lightoj.com_volume_showproblem.php_problem_1099]: http://lightoj.com/volume_showproblem.php?problem=1099