问题标题: 洛谷:P1119 灾后重建 10分求助

0
0
已解决
赵逸凡
赵逸凡
初级启示者
初级启示者

Rt

#include<iostream>
#include<queue>
#include<cstring>
#define MAXN 210
using namespace std;
int n,m,t[MAXN],q,dis[MAXN],ok[MAXN],cnt;
struct node{
    int to,w;
};
typedef pair<int,int> P;
vector<node> g[MAXN];
void dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    priority_queue<P,vector<P>,greater<P> > a;
    dis[s]=0;
    a.push(P(0,s));
    while(!a.empty())
    {
        P p=a.top();
        a.pop();
        int u=p.second;
        if(dis[u]<p.first)
            continue;
        for(int i=0;i<g[u].size();i++)
        {
            node e=g[u][i];
            if(!ok[e.w])
                continue;
            if(dis[e.to]>dis[u]+e.w)
            {
                dis[e.to]=dis[u]+e.w;
                a.push(P(dis[e.to],e.to));
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>t[i];
    for(int i=1;i<=m;i++)
    {
        int u,v,len;
        cin>>u>>v>>len;
        g[u].push_back((node){v,len});
        g[v].push_back((node){u,len});
    }
    for(int i=0;i<n;i++)
    {
        if(!t[i])
            ok[i]=1;
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        for(int j=cnt;j<n;j++)
        {
            if(t[j]>z)
                break;
            if(!ok[i])
                ok[i]=1;
            cnt=j;
        }
        dijkstra(x);
        if(dis[y]==0x3f3f3f3f||t[x]>z||t[y]>z)
            cout<<"-1\n";
        else
            cout<<dis[y]<<endl;
    }
    return 0;
}

求助大佬们哪里错了QAQ


0
已采纳
李源徽
李源徽
新手光能
新手光能

这题我佛洛依德的

0
0
赵逸凡
赵逸凡
初级启示者
初级启示者

@刘景程 你是用什么算法写的?

 

赵逸凡在2020-08-15 15:01:27追加了内容

我当时想时间O(q m log n),如果加优化应该可以勉强过

0
我要回答