最短路题目整理 Poj 2387 + 3259 + 2502 + 1847

冷不防 2021-12-05 02:34 242阅读 0赞

树形DP刷不动了，意识模糊。。总结一下以前做的题。

**Poj 2387 Til the Cows Come Home**

最短路水题，注意重边。

#pragma warning (disable: 4514 4786)
    #include <cstdio>
    #include <cstring> 
    #include <algorithm> 
    #include <queue>
    using namespace std;
    
    const int INF = 0x5fffffff;  //权值上限
    const int MAXPT = 1002;       //顶点数上限
    const int MAXEG = 2*2002;     //边数上限
    
    //点存储1~n
    template<typename Type>
    class Dijkstra     /*邻接表 + 优先队列 + Dijkstra求最短路*/
    {
    private:
    	int n,e;
        Type dis[MAXPT];
    	int head[MAXPT];
        bool visit[MAXPT];
    
        struct Node
    	{
    		int v;
    		Type dis;
            Node () {}
    		Node (int _v,Type _dis)
    		{
    			v=_v;
    			dis=_dis;
    		}
    		bool operator < (const Node a) const
    		{
    			return dis>a.dis;
    		}
    	};
    	
    	struct Edge
    	{
    		int v,next;
    		Type w;
    		Edge () {}
    		Edge (int _v, int _next,Type _w)
    		{
    			v=_v;
    			next=_next;
    			w=_w;
    		}
        }edges[MAXEG];
    
    public:
        inline void init (int _n)
    	{ 
            n = _n;
    		e = 0; 
            memset(head,-1,sizeof(int) * (n+1));
        } 
      
        inline void Add (int u,int v,Type 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");
            } 
        } 
      
        Type 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]; 
        }
    };
    
    Dijkstra<int> ob;
      
    int main ()
    {
    	int n,m;
        while (~scanf("%d%d",&m,&n))
    	{
    		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);
            }
    		printf("%d\n",ob.dijkstra(1,n));
    	}
    	return 0; 
    }

**Poj 3259 Wormholes**

SPFA判环

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int MAXPT = 505; 
    const int MAXEG = 2505*2+300; 
    const int INF = 0x3fffffff;
      
    class SPFA
    {
    private:
    	int n,e; 
        int dis[MAXPT],head[MAXPT];
    	int cnt[MAXPT]; //cnt[i]>n则表示有负环
        bool visit[MAXPT];
    	
        struct Edge
    	{
    		int v,w,next;
    		Edge () {}
    		Edge (int _v, int _next, int _w)
    		{
    			v=_v;
    			next=_next;
    			w=_w;
    		}
        }edges[MAXEG];
    
    public:
        void init (int vn)
    	{ 
            n = vn;
    		e = 0; 
            for (int i=0;i<=n;i++) 
    		{
                head[i] = -1;
                visit[i] = false;
                dis[i] = INF;
    			cnt[i] = 0;
            } 
        } 
      
        inline void Add (int u, int v, int w)
    	{ 
            edges[e] = Edge(v,head[u],w);
            head[u] = e++;
        } 
    
        bool spfa (int src, int des)
    	{ 
            queue<int> que; 
            dis[src] = 0; 
            que.push(src); 
            visit[src] = true; 
            while (!que.empty())
    		{ 
                int u = que.front(); 
                que.pop(); 
                visit[u] = false; 
                for (int i = head[u]; i != -1; i = edges[i].next)
    			{ 
                    int v = edges[i].v;
    				if (dis[v] == INF || dis[u]+edges[i].w < dis[v])
    				{
    					dis[v]=dis[u]+edges[i].w;
    					cnt[u]++;
    					if (cnt[u]>=n)
    						return true;  //负环
    					if (visit[v]==false)
    					{
    						visit[v] = true;
    						que.push(v);
    					}
    				}
    			}
            }
            return false;  //没有负环
        }
    }ob; 
      
    int main ()
    { 
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
        int T;
        scanf("%d",&T);
        for (int Cas=1;Cas<=T;Cas++)
        {
    		int n,m,w,i;
    		scanf("%d%d%d",&n,&m,&w);
            ob.init(n);
            int a, b, c;
    		for (i=0;i<m;i++)
    		{
                scanf("%d%d%d",&a,&b,&c);
                ob.Add(a,b,c);
                ob.Add(b,a,c);
            }
    		for (i=0;i<w;i++)
    		{
                scanf("%d%d%d",&a,&b,&c);
    			c*=-1;
                ob.Add(a,b,c);
            }
    		if (ob.spfa(1,n))
    			printf("YES\n");
    		else
    			printf("NO\n");
        } 
        return 0; 
    }

**Poj 2502 Subway**

题意：在一个城市里，分布着若干条地铁线路，每条地铁线路有若干个站点，所有地铁的速度均为40km/h。现在你知道了出发地和终点的坐标，以及这些地铁线路每个站点的坐标，你的步行速度为10km/h，且你到了地铁的任意一个站之后就刚好有地铁出发。问你从出发点到终点最少需要多少时间。

思路：建图：把起点，终点，以及每个地铁站作为一个图的所有顶点，所有顶点i和j两两之间，均有边权为w = dis / 10 (km/h) 的边相连，任意地铁线路的任意两个相邻的站点，均有边权为 w = dis / 40 (km/h)的边相连。

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm> 
    #include <queue>
    using namespace std;
    
    const double INF = 1e10;  //权值上限
    const int MAXPT = 210;       //顶点数上限
    
    typedef pair <double,int> ele;
    
    class Dijkstra     /*邻接矩阵 + 优先队列 + Dijkstra求最短路*/
    {
    private:
    	double map[MAXPT][MAXPT];
    	bool vis[MAXPT];
    	double dis[MAXPT];
    	int n;
    
    public:
    
    	void init (int num)
    	{
    		n=num;
    		for (int i=0;i<=n;i++)
    			for (int j=0;j<=n;j++)
    			{
    				if (i==j)
    					map[i][j]=0;
    				else
    					map[i][j] = INF;
    			}
    //		memset (dis,0,sizeof(dis));
    		memset (vis,false,sizeof(vis));
    	}
    
    	void Add (int u,int v,double w)
    	{
    		if (w<map[u][v])
    			map[u][v]=w;
    	}
    
    	double dijkstra (int src,int end)
    	{
    		int i;
    		for (i=0;i<=n;i++)
    			dis[i] = INF;
    		dis[src] = 0;
    		priority_queue < ele,vector<ele>,greater<ele> >q;  //优先队列：小顶堆
    		q.push (make_pair(dis[src],src));
    		
    		while ( !q.empty() )
    		{
    			ele t = q.top();
    			q.pop();
    			int now = t.second;
    			if ( vis[now] )
    				continue;
    			vis[now] = true;
    			for (i=1; i<=n; i++)
    				if (vis[i]=false && map[now][i]<INF && dis[i] > dis[now]+map[now][i])
    				{
    					dis[i] = dis[now]+map[now][i];
    					q.push(make_pair(dis[i],i));
    				}
    		}
    		return dis[end];
    	}
    }ob;
    
    int x[MAXPT],y[MAXPT],visit[MAXPT][MAXPT];
    
    int main ()
    {
    	scanf("%d%d%d%d",&x[1],&y[1],&x[2],&y[2]);
    	ob.init (205);
    	int n=3,m=3,u,v;
    	double d;
    	memset(visit,0,sizeof(visit));
    	while (~scanf("%d%d",&u,&v))
    	{
    		if (u==-1 && v==-1)
    		{
    			m=n;
    			continue;
    		}
    		x[n]=u,y[n]=v;
    		if (n!=m)
            {
    			visit[n-1][n]=1;
    			visit[n][n-1]=1;
    			d=sqrt(1.0*(x[n]-x[n-1])*(x[n]-x[n-1])+(y[n]-y[n-1])*(y[n]-y[n-1]))/40000.0;
    			ob.Add (n-1,n,d);
    			ob.Add (n,n-1,d);
    		}
    		n++;
    	}
    	for (int i=1;i<n;i++)
    		for (int j=i+1;j<n;j++)
    			if (visit[i][j] == 0)
    			{
    				d=sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))/10000.0;
    				ob.Add (i,j,d);
    				ob.Add (j,i,d);
                }
    
    	printf("%lf\n",ob.dijkstra(1,2));
    	return 0;
    }

**Poj 1847 Tram**

题意参见：http://blog.csdn.net/zhang20072844/article/details/7761273

#include <cstdio>
    #include <cstring> 
    #include <algorithm> 
    #include <queue>
    using namespace std;
    
    const int INF = 0x5fffffff;  //权值上限  
    const int MAXPT = 102;       //顶点数上限  
    const int MAXEG = 20002;     //边数上限  
    
    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 n,s,e;  
        while (~scanf("%d%d%d",&n,&s,&e))
        {  
            ob.init(n);  
            for (int i=1;i<=n;i++)
    		{
    			int a,b;
    			scanf("%d",&a);
    			for (int j=0;j<a;j++)
    			{
    				scanf("%d",&b);
    				if (j == 0)
    					ob.Add(i,b,0);
    				else
    					ob.Add(i,b,1);
                }  
            }
    		int ans=ob.dijkstra(s,e);
    		if (ans!=INF)
    			printf("%d\n",ans);
    		else
    			printf("-1\n");
        }  
        return 0;   
    }