1003 Emergency (25)

输入城市数量，道路数量，出发城市，目的城市
每座城市的救援队数量
每条路连接的城市和路长
输出两个数字
第一个是有多少条最短的路 第二个是路长最多有多少支救援队
先建立邻接矩阵 然后搜索就行了，记录当前路长和路上救援队的数量，和最短路长比较，最后输出。

#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define INF 0x3fffffff

using namespace std;

int n,m,c1,c2,a,b,l,pic[501][501],vis[501],minl,rscnt,rs[501],s,rescnt,way;

void dfs(int a)
{
    vis[a]=1;
    rscnt+=rs[a];
    if (a==c2)
    {
        if (s<minl)
        {
            rescnt=rscnt;
            way=1;
            minl=s;
        }
        else if (s==minl)
        {
            way+=1;
            rescnt=max(rescnt,rscnt);
        }
        return;
    }
    else
    {
        for (int i=0;i<n;i++)
        {
            if(pic[a][i]!=INF&&vis[i]==0)
            {
                s+=pic[a][i];
                dfs(i);
                rscnt-=rs[i];
                s-=pic[a][i];
                vis[i]=0;
            }
        }
        return;
    }
}


int main()
{
    memset(pic,0,sizeof(pic));
    memset(vis,0,sizeof(vis));
    memset(rs,0,sizeof(rs));
    for (int i=0;i<501;i++)
    {
        for (int j=0;j<501;j++)
            pic[i][j]=INF;
    }
    cin>>n>>m>>c1>>c2;
    for (int i=0;i<n;i++)
        cin>>rs[i];
    minl=INF;
    rscnt=0;
    s=0;
    way=1;
    rescnt=0;
    while (m--)
    {
        cin>>a>>b>>l;
        pic[a][b]=pic[b][a]=l;
    }
    dfs(c1);
    cout<<way<<' '<<rescnt<<endl;
}