HDU_4725_思维建图+最短路

HDU 4725

  • 难点是如何将楼层转化到图中,
  • 用2个点将一个面(楼层)抽象出来,1个入点,1个出点
  • 一个面上的所有点都指向出点,权值为0
  • 入点指向该面所有的点(除了出点),权值为0
  • 入点指向出点,权值为0,
  • 中间的楼层的出点分别指向上一层的入点和下一层的入点,权值为c.将所有楼层都连接起来
  • 没有最短路则dist[n] = MAX
  1. dij
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    #include <iostream>
    #include <string.h>
    #include <queue>
    #include <vector>
    #include <cmath>
    using namespace std;
    const int maxn = 3e5+5;
    const int MAX = 0x3f3f3f3f;

    vector<pair<int,int> > e[maxn];
    int n,m,cost;
    int dist[maxn];

    int dij() {
    	priority_queue<pair<int,int> > que;
    	memset(dist,0x3f,sizeof dist);
    	que.push( make_pair(0,1) );
    	dist[1] = 0;
    	while (!que.empty()) {
    		int cur = que.top().second; que.pop();
    		for (int i=0; i<e[cur].size(); i++) {
    			int to = e[cur][i].first;
    			int div = e[cur][i].second;
    			if (dist[to] > dist[cur] + div) {
    				dist[to] = dist[cur] + div;
    				que.push( make_pair(-dist[to],to) );
    			}
    		}
    	}
    	return dist[n];
    }

    int main() {
    //	freopen("a.txt","r",stdin);
    	int times,k=0;
    	scanf("%d",&times);
    	while (times--) {
    		scanf("%d%d%d",&n,&m,&cost);
    		// 楼层抽象化成2个点,一个入点，一个出点
    		int temp;
    		for (int i=1; i<=n; i++) { //i代表点,temp是该点的楼层
    			scanf("%d",&temp);
    			e[temp*2+n-1].push_back( make_pair(i,0) ); // 入点指向平面的点
    			e[i].push_back( make_pair(temp*2+n,0) ); // 平面中的点指向出点
    		}
    		// 每个点之间的边
    		int from,to,div;
    		for (int i=1; i<=m; i++) {
    			scanf("%d%d%d",&from,&to,&div);
    			e[from].push_back( make_pair(to,div) );
    			e[to].push_back( make_pair(from,div));
    		}
    		// 当前层的 出点 与 相邻层的 入点 建边
    		for (int i=1; i<=n; i++) {
    			from = 2 * i + n; // 出点
    			if (i > 1) {
    				to = from - 3;
    				// 该层的出点,到上一层的入点
    				e[from].push_back( make_pair(to,cost) );
    			}
    			if (i < n) {
    				to = from + 1;
    				// 该层的出点,到下一层的入点
    				e[from].push_back( make_pair(to,cost) );
    			}
    		}
    		int ans = dij();
    		if (ans == MAX) printf("Case #%d: -1\n",++k);
    		else printf("Case #%d: %d\n",++k,ans);

    		// 清除上一组数据
    		for (int i=1; i<=3 * n; i++) e[i].clear();
    	}
    	return 0;
    }
  2. spfa
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    #include <iostream>
    #include <string.h>
    #include <queue>
    #include <vector>
    #include <cmath>
    using namespace std;
    const int maxn = 3e5+5;
    const int MAX = 0x3f3f3f3f;

    vector<pair<int,int> > e[maxn];
    int n,m,cost;
    int dist[maxn];
    bool vis[maxn];

    int spfa() {
    	queue<int> que;
    	memset(vis,0,sizeof vis);
    	memset(dist,0x3f,sizeof dist);
    	que.push(1);
    	dist[1] = 0; vis[1] = 1;
    	while (!que.empty()) {
    		int cur = que.front(); que.pop();
    		vis[cur] = 0;
    		for (int i=0; i<e[cur].size(); i++) {
    			int to = e[cur][i].first;
    			int div = e[cur][i].second;
    			if (dist[to] > dist[cur] + div) {
    				dist[to] = dist[cur] + div;
    				if (!vis[to]) {
    					vis[to] = 1;
    					que.push(to);
    				}
    				
    			}
    		}
    	}
    	return dist[n];
    }

    int main() {
    //	freopen("a.txt","r",stdin);
    	int times,k=0;
    	scanf("%d",&times);
    	while (times--) {
    		scanf("%d%d%d",&n,&m,&cost);
    		// 楼层抽象化成2个点,一个入点，一个出点
    		int temp;
    		for (int i=1; i<=n; i++) { //i代表点,temp是该点的楼层
    			scanf("%d",&temp);
    			e[temp*2+n-1].push_back( make_pair(i,0) ); // 入点指向平面的点
    			e[i].push_back( make_pair(temp*2+n,0) ); // 平面中的点指向出点
    		}
    		// 每个点之间的边
    		int from,to,div;
    		for (int i=1; i<=m; i++) {
    			scanf("%d%d%d",&from,&to,&div);
    			e[from].push_back( make_pair(to,div) );
    			e[to].push_back( make_pair(from,div));
    		}
    		// 当前层的 出点 与 相邻层的 入点 建边
    		for (int i=1; i<=n; i++) {
    			from = 2 * i + n; // 出点
    			if (i > 1) {
    				to = from - 3;
    				// 该层的出点,到上一层的入点
    				e[from].push_back( make_pair(to,cost) );
    			}
    			if (i < n) {
    				to = from + 1;
    				// 该层的出点,到下一层的入点
    				e[from].push_back( make_pair(to,cost) );
    			}
    		}
    		int ans = spfa();
    		if (ans == MAX) printf("Case #%d: -1\n",++k);
    		else printf("Case #%d: %d\n",++k,ans);

    		// 清除上一组数据
    		for (int i=1; i<=3 * n; i++) e[i].clear();
    	}
    	return 0;
    }

算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！