Comment

Musher: 2022-11-23 17:22:55

用了dp，循环次数也不多，就是套了递归，估计是递归的问题，一直TE

//鉴于使用循环更新存在更新顺序的问题 所以使用递归的方式重写 以避免更新顺序问题
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
int maxn = 0x7fffffff;
//全写成全局变量 方便使用
int T;
int n, E, s, t, M; //n个国家，E条道路，从s国去t国，有M块钱
int price[501]; //n个国家的过路费
// int road[501][501]; // 记录国家之间的道路距离，虽然两个国家之间可能存在多条道路，但是只保存最短的就好，因为保存更长的没意义
map<int, int> road[501]; // 更改road的数据结构，从而去掉遍历，road[i]={j,k}表示从i能去j，路途为k
// int dp1[501][101]; // dp1[i][j] 从i国出发，手握j块钱，去目标国家的最短路径

int dp(int i, int k){ // 从i国出发，手握k块钱，去目标国家的最短路径
    // cout << "正在调用dp(" << i << ", " << k << ")" << endl;
    if (i == t) return 0; // 从t国出发，到t国，最短路径自然是0
    else{
        int temp = maxn;
        map<int, int>::iterator road_iter;
        road_iter = road[i].begin();
        while(road_iter != road[i].end()){
            int j = road_iter->first; // 即i能前往j
            if(k>=price[j]){ //当前剩下的钱得够去
                // cout << "现在的price["<< j << "]为：" << price[j] << "k为：" << k << endl;
                // cout << "原来temp为：" << temp << endl;
                if(dp(j, k-price[j]) != -1){ // 子问题返回-1，说明无解
                    temp = min(dp(j, k-price[j]) + road_iter->second, temp);
                }
                // cout << "现在temp为:" << temp << endl; 
            }
            road_iter ++;
            cout << "循环了一次" << endl;
            
        }
        if (temp != maxn) return temp;
        else return -1;
    }
}

int main(){
    cin >> T;
    while(T--){
        for (int i = 0; i < 501; i ++){
            price[i] = 0;
            road[i].clear();
        }
        cin >> n >> E >> s >> t >> M;
        // for (int i = 0; i < 101; i ++){
        //     dp1[t][i] = 0; //因为目的地是t国，所以从t国出发，其最短路径一定是0
        // }
        for (int i = 1; i < n + 1; i ++){
            cin >> price[i];
        } 
        for (int i = 0; i < E; i ++){
            // cout << "正在输入第" << i << "条道路" << endl;
            int u, v, length = 0;
            cin >> u >> v >> length;
            // road[u][v] = min(road[u][v], length); //保存两个国家之间的最短道路
            if (road[u][v]) {
                // cout << "road[" << u << "][" << v << "]值已存在，为: " << road[u][v] << endl;
                // cout << "length为：" << length << endl;
                road[u][v] = min(road[u][v], length); //如果已经有值，则比较大小
            }
            else {
                // cout << "road[" << u << "][" << v << "]值还不存在，准备插入v: " << v << ", length: " << length << endl;
                road[u][v] = length;
            }
            // cout << "road[" << u << "][" << v << "]的值为：" << road[u][v] << endl;
        }
        // map <int, int>::iterator iter;
        // iter = road[1].begin();
        // while(iter != road[1].end()){
        //     cout << iter->first << " " << iter->second << endl;
        //     iter ++;
        // }
        cout << dp(s, M) << endl;
    }
}

09020218刘骐: 2022-05-13 21:15:18

我用的迪杰拉斯特算法为啥做不出来啊啊，我电脑测试结果没错，但一提交就出错
代码如下
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;
pair<int,int> Dijkstra(int s,int t,int**matrix,int n,int *tax)
{
    if(s==t)
    return pair<int,int>(0,0);
    else{
    vector<int>dis(n+1,2147483647-1);
    int price=0;
    int *isSelected=new int[n+1]();
    isSelected[s]=0;
    for(int i=1;i<=n;i++)
    {
        dis[i]=matrix[s][i];
    }
    dis[s]=0;
    for(int i=1;i<=n;i++)
    {
        int node=-1;
        for(int j=1;j<=n;j++)
        {
            if(isSelected[j]==0)
            if(node==-1||dis[j]<dis[node])
            node=j;
        }
        for(int j=1;j<=n;j++)
        {
           if(dis[j]>dis[node]+matrix[node][j])
           {
               dis[j]=dis[node]+matrix[node][j];
               price+=tax[node];
           }
        }
        isSelected[node]=1;
    }
    price+=tax[t];
    delete []isSelected;
    return pair<int,int>(dis[t],price);
    }
}
int main()
{
    int total;
    cin>>total;
    for(int k=0;k<total;k++)
    {
    int n,v,s,t,M;
    cin>>n>>v>>s>>t>>M;
    int **matrix=new int*[n+1];
    int *tax=new int[n+1]();
    for(int i=1;i<=n;i++)
    cin>>tax[i];
    for(int i=1;i<=n;i++)
    {
        matrix[i]=new int[n+1];
        for(int j=1;j<=n;j++)
        matrix[i][j]=2147483647-1;
    }
    for(int i=1;i<=v;i++)
    {
        int u,t,w;
        cin>>u>>t>>w;
        matrix[u][t]=min(w,matrix[u][t]);
    }
    pair<int,int>result=Dijkstra(s,t,matrix,n,tax);
    if(result.first==2147483647-1||result.second>M||result.first<0)
    cout<<-1<<endl;
    else
    cout<<result.first<<endl;
    //  delete[]tax;
    // for(int l=0;l<=n;l++)
    // delete[]matrix[l];
    // delete[]matrix;
    }
}

LeonWong: 2021-12-28 13:16:46

多谢copker大佬

copker: 2021-12-27 13:40:09

直接广搜

zcw8887: 2020-11-21 12:31:04

直接做有困难的话可以先做1028和1029，这几题思路有类似之处，而且代码也可以部分重用。1023时间复杂度要求比较严，注意减少重复的遍历。