poj2353Ministry(链式前向星+堆优化dijkstra)

题目链接：http://poj.org/problem?id=2353

题目大意：有M层楼，每层楼有N个房间，每次到一个房间都有一个花费，有三个规定，1，你需要从第一层开始走，2，房间号相同时，才能上下移动，3，相邻的房间，可以互相通往，要求你求从第一层开始，到最后一层，所花费的最小代价。输出所经过的房间的房间号。

思路：这个题我觉得主要考察的是如何建图，其实图也不难建，就是有点小麻烦，有很多地方也需要注意。建图只需要按照题目规定的，上下房间连通，相邻的房间连通，建立一个图（建图的时候用vector建会超时，所以我用的链式前向星建的图），建完图后直接跑dijkstra就行了，还有就是，这个题没有固定的出发点和终点，需要自己想象一个出发点和终点，出发点都连到一层楼房间上，所有最后一层房间都连通到重点，然后跑dijkstra的时候存一下点，最后输出这些点就ok了。

代码：

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include<string>
  6 #include
  7 #include
  8 #include
  9 #include
 10 #define inf 0x3f3f3f3f
 11 #define ll long long
 12 using namespace std;
 13 const int N = 1000 + 10;
 14 const int M = 500 + 10;
 15 const int MAXN = N * M + 10;
 16 
 17 int dis[MAXN];
 18 int vis[MAXN];
 19 int n, m, s;
 20 int w[N][M];
 21 int nod[MAXN];
 22 
 23 struct point {
 24     int dis;
 25     int pos;
 26     bool operator <(const point& x)const
 27     {
 28         return x.dis < dis;
 29     }
 30 };
 31 //priority_queuepq;
 32 
 33 //struct node {
 34 //    int to, val;
 35 //};
 36 //vectorG[MAXN];
 37 
 38 struct node {
 39     int to, w, next;
 40 }edge[MAXN];
 41 int head[MAXN];
 42 int cnt;
 43 
 44 void add(int u, int v, int w)
 45 {
 46     edge[cnt].w = w;
 47     edge[cnt].to = v;
 48     edge[cnt].next = head[u];
 49     head[u] = cnt++;
 50 }
 51 
 52 void dijkstra(int t) {
 53 
 54     for (int i = 0; i <= (n + 1) * m; i++) dis[i] = inf;
 55     memset(vis, 0, sizeof(vis));
 56     dis[t] = 0;
 57     priority_queuepq;
 58     /*point h;
 59     h.dis = 0, h.pos = t;*/
 60     pq.push({ 0,t });
 61     while (!pq.empty()) {
 62         point tmp = pq.top();
 63         pq.pop();
 64         int p = tmp.pos, d = tmp.dis;
 65         if (vis[p]) continue;
 66         vis[p] = 1;
 67         for (int i = head[p]; i != -1; i = edge[i].next) {
 68             int frt = edge[i].to, dist = edge[i].w;
 69             if (!vis[frt] && dis[p] + dist < dis[frt]) {
 70                 dis[frt] = dis[p] + dist;
 71                 //hh.dis = dis[frt], hh.pos = frt;
 72                 pq.push({ dis[frt],frt });
 73                 nod[frt] = p;
 74             }
 75         }
 76     }
 77     //return dis[n];
 78 }
 79 
 80 void print(int s) {
 81     if (nod[s] != 1) {
 82         print(nod[s]);
 83         if (nod[s] % m == 0) {
 84             printf("%d\n", m);
 85             //cout << m << "\n";
 86         }
 87         else {
 88             printf("%d\n", nod[s] % m);
 89             //cout << nod[s] % m << "\n";
 90         }
 91     }
 92 }
 93 
 94 int main() {
 95 
 96     /*ios::sync_with_stdio(false);
 97     cin.tie(0);*/
 98     //int  n, m;
 99     scanf("%d %d", &n, &m);
100     memset(head, -1, sizeof(head));
101     for (int i = 1; i <= n; i++) {
102         for (int j = 1; j <= m; j++) {
103             scanf("%d", &w[i][j]);
104         }
105     }
106     for (int i = 1; i <= n; i++) {
107         for (int j = 1; j < m; j++) {
108             if (i != 1 && i != n) {
109                 /*G[i * m + j].push_back({ i * m + j + 1, w[i][j + 1] });
110                 G[i * m + j + 1].push_back({ i * m + j, w[i][j] });*/
111                 add(i * m + j, i * m + j + 1, w[i][j + 1]);
112                 add(i * m + j + 1, i * m + j, w[i][j]);
113             }
114         }
115         if (i != n) {
116             for (int j = 1; j <= m; j++) {
117                 //G[i * m + j].push_back({ (i + 1) * m + j,w[i + 1][j] });
118                 add(i * m + j, (i + 1) * m + j, w[i + 1][j]);
119             }
120         }
121     }
122     for (int i = 1; i <= m; i++) {
123         //G[1].push_back({ m + i,w[1][i] });
124         add(1, m + i, w[1][i]);
125     }
126     for (int i = 1; i <= m; i++) {
127         //G[n * m + i].push_back({ 0,0 });
128         add(n * m + i, 0, 0);
129     }
130     //int ans = inf;
131     //for (int i = 1; i <= m; i++) {
132     //    //ans = min(ans, dis[n * m + i]);
133     //    cout << dis[n * m + i] << " ";
134     //}
135     dijkstra(1);
136     //cout << dis[0] << "\n";
137     //cout << ans << "\n";
138     print(0);
139 
140     return 0;
141 }
 
最短路问题

相关

最短路问题——弗洛伊德算法(Floyd)

最短路问题

标签