CODE[VS]1021 玛丽卡

题目：http://codevs.cn/problem/1021/
思路：使用floyd算法求解最优时间，并记录在不堵车情况（理想状态）下最优路径。枚举所有路径上的道路，计算在该路径无法通过时的最优时间，记录最长的最优时间。道路为双向车道，所以一条道路数据代表两条不同的道路。如果到达城市b的道路有m条，则b出现在floyd处理队列的次数可能为m。

题解：

/* 1021 玛丽卡 */
#include <stdio.h>

#define DEBUG

#define MAXN 1001           /* 最大城市数 */ 
#define MAXM 1000000        /* 最多道路数 */
#define MAXV 1001           /* 最长通过时间 */
#define JAMF -1             /* 道路无法通过标识 */ 
#define ALLM 1000000        /* 所有道路时间总和 */ 

/* 道路列表 */
struct _road{
    int a;      /* 出发城市 a */     
    int b;      /* 到达城市 b */ 
    int v;      /* 使用时间 v */ 
    int next;   /* 城市a下一条道路编号 */ 
    int city;   /* 城市a第一条道路编号 */ 
}roads[MAXM]; 

int queue[MAXM], inq[MAXN];     /* 待操作城市队列, 是否已存在于操作队列标识 */ 
int vtime[MAXN], father[MAXN];  /* 距离起点距离列表，到达当前城市道路列表 */ 
int city_head[MAXN];            /* 城市第一条道路编号 */ 


int n, m;       /* 城市数，道路数 */ 
int rc;         /* 总道路计数 */ 
int maxv;       /* 最长通过时间 */ 

/* 添加道路到城市 */
void add_road(int a, int b, int v){
    rc++;
    /* 添加新道路 */ 
    roads[rc].a = a;
    roads[rc].b = b;
    roads[rc].v = v;
    roads[rc].next = city_head[a];  /* 当前道路的下一条道路指向原第一条道路 */ 
    city_head[a] = rc;              /* 第一条道路编号更新为当前道路 */ 
} 

/* 获取城市a到b的最短时间，并记录理想状态下的最优路径 */
void get_shortest(int p){
    int a, b, v;    /* 出发城市，到达城市，使用时间 */ 
    int t, w;       /* 当前操作城市位置，总待操作城市数量 */ 
    int r;          /* 城市道路编号 */ 
    /* 初始化操作城市列表 */ 
    queue[0] = 1;
    vtime[1] = 0;
    inq[1] = 1;
    t = 0;
    w = 1;
    /* 初始化所有城市状态 */ 
    for(a = 2; a <= n; a++){
        inq[a] = 0;
        vtime[a] = ALLM;
    }
    /* FLOYD 算法求解最优路径 */ 
    while(t < w){
        a = queue[t];   /* 当前操作城市 */ 
        t++; 
        /* 获取城市第一条道路，并遍历所有其相连道路 */
        r = city_head[a];    
        while(r > 0){
            b = roads[r].b;
            /* 如果通过道路r到达b的时间优于原时间，更新b的最优时间 */ 
            if(roads[r].v != JAMF && vtime[a] + roads[r].v < vtime[b]){
                vtime[b] = vtime[a] + roads[r].v;
                /* 如果城市b不在待操作队列中，则将其加入到队列 */ 
                if(0 == inq[b]){
                    inq[b] == 1;
                    queue[w] = b;
                    w++;
                }
                /* 如果是理想状态，则记录最优路径 */ 
                if(p == 1){
                    father[b] = r;
                }
            }
            /* 操作城市下一条道路 */ 
            r = roads[r].next;
        }
        /* 将城市a从待操作队列中移除 */ 
        inq[a] = 0;
    } 
} 

/* 主函数入口 */ 
int main(int argc, char *argv[]) {
    int a, b, v;        /* 城市a，b，道路通过时间 */
    int i;              /* 索引值 */ 
#ifdef DEBUG
    FILE *fp;
    if(NULL == (fp = fopen("data.txt", "r"))){
        return 1;
    } 
#endif
    /* 获取城市数，道路数 */
#ifdef DEBUG
    fscanf(fp, "%d %d", &n, &m);
#else
    scanf("%d %d", &n, &m);
#endif
    /* 初始化道路编号和城市第一条道路编号 */ 
    rc = 0; 
    for(i = 1; i <= n; i++){
        city_head[i] = 0;
    }
    /* 获取道路 */
    for(i = 0; i < m; i++){
#ifdef DEBUG
        fscanf(fp, "%d %d %d", &a, &b, &v);
#else
        scanf("%d %d %d", &a, &b, &v);
#endif
        /* 添加道路到城市，双向车道添加两次 */ 
        add_road(a, b, v);
        add_road(b, a, v);
    } 
    /* 获取理想状态下最优路时间和路径 */ 
    get_shortest(1);
    maxv = vtime[n];
    /* 遍历理想状态下最优路径可能的堵车路段 */ 
    a = n;
    while(a != 1){
        v = roads[father[a]].v;
        roads[father[a]].v = JAMF;
        get_shortest(0);
        if(vtime[n] > maxv){
            maxv = vtime[n];
        }   
        roads[father[a]].v = v; 
        a = roads[father[a]].a;
    }
    /* 输出计算结果 */    
    printf("%d", maxv);
#ifdef DEBUG
    fclose(fp);
#endif
    return 0;
}

最后

以上就是满意黑米为你收集整理的CODE[VS]1021 玛丽卡的全部内容，希望文章能够帮你解决CODE[VS]1021 玛丽卡所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。