PAT甲级1003.

目录

#　A1003

题目

样例

输入：

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

输出:

2 4

思路和坑点

　　直接使用Dijkstra+dfs计算路径，没得到一条路径就进行统计，然后根据第二尺度进行优化。其实一遍Dijkstra算法应该可以，但是判定逻辑可能不是很好理清楚。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 505
#define INF 0x3fffffff
int G[MAXN][MAXN];
int weight[MAXN]={0};
bool vis[MAXN]={false};
int dis[MAXN];
vector<int> pre[MAXN];
int st,ed,n,m,ansnum=0,answ=0;
vector<int> temppath;
void Dijkstra(){
    fill(dis,dis+MAXN,INF);
    dis[st]=0;
    for(int i=0;i<n;i++){
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&dis[j]<MIN){
                u=j;
                MIN=dis[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF){
                if(dis[u]+G[u][v]<dis[v]){
                    dis[v]=dis[u]+G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if(dis[u]+G[u][v]==dis[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }

}
void dfs(int s){
    if(s==st){
        ansnum++;
        temppath.push_back(s);
        int val=0;
        for(int i=0;i<temppath.size();i++){
            val+=weight[temppath[i]];
        }
        answ=max(answ,val);
        temppath.pop_back();
        return;
    }
    temppath.push_back(s);
    for(int i=0;i<pre[s].size();i++){
        dfs(pre[s][i]);
    }
    temppath.pop_back();
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    fill(G[0],G[0]+MAXN*MAXN,INF);
    cin>>n>>m>>st>>ed;
    for(int i=0;i<n;i++){
        scanf("%d",&weight[i]);
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        G[a][b]=G[b][a]=c;
    }
    Dijkstra();
    dfs(ed);
    cout<<ansnum<<' '<<answ;
    return 0;
}