复试机试第二天

  1. Dijkstra算法
  2. #define INF 1000000
    using namespace std;
    const int MAXN = 505;
    int N;
    int grapth[MAXN][MAXN];
    int dis[MAXN];
    bool vis[MAXN];
    int res;
    void Dijkstra(int start_point) {
        fill(dis, dis + N + 1, INF);
        memset(vis, 0, sizeof(vis));
    
        dis[start_point] = 0;
        for (int i = 0; i < N; i++) {//循环N次
            int u = -1;
            int min_dis = INF;
            for (int j = 1; j <= N; j++) {
                if (vis[j] == false && min_dis > dis[j]) {
                    u = j;
                    min_dis = dis[j];
                }
            }
                if (u == -1) return;
                vis[u] = true;
                for (int k = 1; k <= N; k++) {
                    if (vis[k] == false&& grapth[u][k]!=INF && dis[u] + grapth[u][k] < dis[k]) {    
                        dis[k] = dis[u] + grapth[u][k];
                    }
                }
            }
    }

    在调试的过程中,由于括号打错,使得整个算法出现莫名其妙的结果非常遗憾的浪费了大量的时间,哎pat只得2分,不知道机试能得几分。

上一篇:JavaWeb学习--MySql数据库(DDL)


下一篇:PTA 1015 Reversible Primes