现在的位置: 首页 > 综合 > 正文

PAT 1003. Emergency

2018年04月25日 ⁄ 综合 ⁄ 共 1312字 ⁄ 字号 评论关闭
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<cstring>
using namespace std;
int mp[510][510];
int d[510];
int res[510];
int st;
int ed;
vector<int> pre[510];
int m;
int n;
bool f[510];
int cnt=0;
void input()
{
    scanf("%d %d %d %d",&n,&m,&st,&ed);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&res[i]);
       // pre[i].push_back(i);
       // d[i]=0x3f3f3f3f;
    }
    pre[st].push_back(st);

    int a,b,c;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        mp[a][b]=mp[b][a]=c;
    }
}
void dijkstra()
{
    memset(d,0x3f,sizeof(d));
	memset(f,true,sizeof(f));
	int N=n;
    d[st]=0;
    while(N--)
    {
        int min=0x3f3f3f3f;
        int u=0;
        for(int i=0;i<n;i++)
        {
            if(f[i]==true&&d[i]<min)
            {
                min=d[i];
                u=i;
            }
        }
        if(min==0x3f3f3f3f) break;
        f[u]=false;
        for(int v=1;v<n;v++)
        {
            if(mp[u][v]!=0)
            {
                //if(f[v]&&d[v]>d[u]+mp[u][v])
                if(d[v]>=d[u]+mp[u][v])
                {
                    d[v]=d[u]+mp[u][v];
                    pre[v].push_back(u);
                }
            }
        }


    }
//    for(int i=0;i<n;i++) cout<<d[i]<<" ";
//    cout<<endl;
//    cout<<"pre:  "<<endl;
//    for(int i=0;i<n;i++)
//    {
//        for(int j=0;j<pre[i].size();j++)
//        {
//            cout<<pre[i][j]<<" ";
//        }
//        cout<<endl;
//    }
}
int ans=0;
int mx=0;
void get(int n)
{
    if(n==ed)
    {
        mx+=res[n];
    }
    if(pre[n][0]==n)
    {
       // mx+=res[n];
        cnt++;
        if(mx>ans)
        {
            ans=mx;
        }
        return;
    }
    else
    {
        for(int i=0;i<pre[n].size();i++)
        {
            mx+=res[pre[n][i]];
            get(pre[n][i]);
            mx-=res[pre[n][i]];
        }
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    input();
    dijkstra();
    get(ed);
    printf("%d %d\n",cnt,ans);
    return 0;
}

提交了两次一直CE,error:reference to 'prev' is ambiguous

原因是prev重名了。

抱歉!评论已关闭.