像鱼583 2021-10-19 22:23 采纳率: 66.7%
浏览 21
已结题

pta甲级题1111,不知道哪出错了运行不了


#include<iostream>
using namespace std;
#include<algorithm>
int n, m;
int es[510][510], et[510][510], diss[510], dist[510], books[510], bookt[510];
#include<vector>
vector<int>temppath, path, temptime, timepath, pres[510], pret[510];
int start, jieshu;
const int inf = 99999999;
int minstime = inf;
int mincount = inf;
int minlength = inf;
int minstime2 = inf;
//求最短路径的dfs
void dfss(int v) {
    temppath.push_back(v);
    if (v == start) {
        int stime = 0, length = 0;
        for (int i = temppath.size() - 1; i >= 1; i--) {
            int id = temppath[i];
            int nextid = temppath[i - 1];
            length += es[id][nextid];
            stime += et[id][nextid];
        }
        if (length < minlength) {
            minlength = length;
            if (stime < minstime) {
                minstime = stime;
                path = temppath;
            }
        }
    }
    for (int i = 0; i < pres[v].size() - 1; i++) {
        dfss(pres[v][i]);
    }
    temppath.pop_back();
}
void dfst(int v) {
    
    temptime.push_back(v);
    if (v == start) {
        int count = 0, stime = 0;
        for (int i = temppath.size() - 1; i >= 1; i--) {
            int id = temppath[i];
            int nextid = temppath[i - 1];
            count++;
            stime += et[id][nextid];
        }
        if (count < mincount) {
            mincount = count;
            if (stime < minstime2) {
                minstime2 = stime;
                timepath = temptime;
            }
        }
    }
    for (int i = 0; i < pret[v].size() - 1; i++) {
        dfst(pret[v][i]);
    }
    temptime.pop_back();
}
int main()
{
    cin >> n, m;
    fill(es[0], es[0] + 510 * 510, inf);
    fill(et[0], et[0] + 510 * 510, inf);
    fill(diss, diss + 510, inf);
    fill(dist, dist + 510, inf);
    //现在开始输入每个结点之间的距离和时间关系
    int v1, v2, o, s, t;
    for (int i = 0; i < m; i++) {
        cin >> v1 >> v2 >> o >> s >> t;
        if (o == 1)//说明是单行道
        {
            es[v1][v2] = s;
            et[v1][v2] = t;
        }
        else if (o == 0)//说明是双行道
        {
            es[v1][v2] = s;
            es[v2][v1] = s;
            et[v1][v2] = t;
            et[v2][v1] = t;
        }
    }
    //现在输出起始点
    cin >>start >> jieshu;
    //先从最短路径开始搞起
    diss[start] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        int minn = inf;
        for (int j = 0; j < n; j++) {
            if (books[j] == 0 && diss[j] < minn) {
                minn = diss[j];
                u = j;
            }
        }
            if (u == -1) {
                break;
            }
            books[u] = 1;
            for (int v = 0; v < n; v++) {
                if (books[v] == 0 && es[u][v] != inf) {
                    if (diss[v] > diss[u] + es[u][v]) {
                        diss[v] = diss[u] + es[u][v];
                        pres[v].clear();
                        pres[v].push_back(u);
                    }
                    else if (diss[v] == diss[u] + es[u][v]) {
                        pres[v].push_back(u);
                    }
                }
            }
        }
    //现在开始dfs求最短路径
    dfss(jieshu);
    //现在开始求最短时间
    dist[start] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        int minn = inf;
        for (int j = 0; j < n; j++) {
            if (bookt[j] == 0 && dist[j] < minn) {
                minn = dist[j];
                u = j;
            }
        }
        if (u == -1) {
            break;
        }
        bookt[u] = 1;
        for (int v = 0; v < n; v++) {
            if (bookt[v] == 0 && et[u][v] != inf) {
                if (dist[v] > dist[u] + et[u][v]) {
                    dist[v] = dist[u] + et[u][v];
                    pret[v].clear();
                    pret[v].push_back(u);
                }
                else if (dist[v] == dist[u] + et[u][v]) {
                    pret[v].push_back(u);
                }
            }
        }
    }
    //现在dfs
    dfst(jieshu);
    //现在判断最短路径和最短时间的是不是同一个
    int index = 1;
    for (int i = 0; i < path.size() - 1; i++) {
        if (path[i] == timepath[i]) {
            index = 0;
        }
    }
    if (index == 1)//说明两条路不相等
    {
        cout << "Distance = " << diss[jieshu] << ": " << start;
        for (int i = path.size() - 2; i >= 0; i--) {
            cout << "->" << path[i];
        }
        cout << endl;
        cout << "Time = " << minstime << ": "<<start;
        for (int i = timepath.size() - 2; i >= 0; i--) {
            cout << "->" << timepath[i];
        }
    }
    else if (index == 0) {
        cout << "Distance =" << diss[jieshu] << ": " << "Time = " << minstime << ": "<<start;
        for (int i = path.size() - 2; i >= 0; i--) {
            cout << "->" << path[i];
        }

    }
    cout << endl;
    system("pause");
    return 0;
}
  • 写回答

1条回答 默认 最新

  • 仰望星空的代码 博客专家认证 2021-10-20 15:53
    关注

    把报错信息贴出来

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 10月28日
  • 已采纳回答 10月20日
  • 创建了问题 10月19日

悬赏问题

  • ¥15 请问有人会紧聚焦相关的matlab知识嘛?
  • ¥15 网络通信安全解决方案
  • ¥50 yalmip+Gurobi
  • ¥20 win10修改放大文本以及缩放与布局后蓝屏无法正常进入桌面
  • ¥15 itunes恢复数据最后一步发生错误
  • ¥15 关于#windows#的问题:2024年5月15日的win11更新后资源管理器没有地址栏了顶部的地址栏和文件搜索都消失了
  • ¥100 H5网页如何调用微信扫一扫功能?
  • ¥15 讲解电路图,付费求解
  • ¥15 有偿请教计算电磁学的问题涉及到空间中时域UTD和FDTD算法结合的
  • ¥15 three.js添加后处理以后模型锯齿化严重