#include#include#include#include#include#include#include#include#include#include#" />

日韩久久久精品,亚洲精品久久久久久久久久久,亚洲欧美一区二区三区国产精品 ,一区二区福利

zju 1003. Emergency (25)

系統(tǒng) 2622 0

http://pat.zju.edu.cn/contests/pat-a-practise/1003

最短路

代碼:

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<string>

#include<queue>

#include<stack>

#include <iomanip>

using namespace std;

#define LL long long

const double eps=1e-6;

const int INF=0x3f3f3f3f;

const int N=505;

int road[N][N];

int a[N];

int dist[N];

int num[N];

int teams[N];

bool had[N];

void dijkstra(int n,int c1,int c2)

{

    for(int i=0;i<n;++i)

    dist[i]=INF;

    memset(num,0,sizeof(num));

    memset(teams,0,sizeof(teams));

    memset(had,false,sizeof(had));

    teams[c1]=a[c1];

    num[c1]=1;

    dist[c1]=0;

    for(int w=0;w<n;++w)

    {

        int k=-1;

        for(int i=0;i<n;++i)

        if(!had[i]&&(k==-1||dist[i]<dist[k]))

        k=i;



        if(k==c2)

        break;

        had[k]=true;

        for(int i=0;i<n;++i)

        if(!had[i])

        {

            if(dist[i]>dist[k]+road[k][i])

            {

                dist[i]=dist[k]+road[k][i];

                num[i]=num[k];

                teams[i]=a[i]+teams[k];

            }else if(dist[i]==dist[k]+road[k][i])

            {

                num[i]+=num[k];

                if(teams[i]<a[i]+teams[k])

                teams[i]=a[i]+teams[k];

            }

        }

    }

}

int main()

{

    //freopen("data.in","r",stdin);

    int n,m,c1,c2;

    while(cin>>n>>m>>c1>>c2)

    {

        for(int i=0;i<N;++i)

        for(int j=0;j<N;++j)

        road[i][j]=INF;

        for(int i=0;i<n;++i)

        cin>>a[i];

        while(m--)

        {

            int l,r,k;

            cin>>l>>r>>k;

            road[l][r]=road[r][l]=min(road[l][r],k);

        }

        dijkstra(n,c1,c2);

        cout<<num[c2]<<" "<<teams[c2]<<endl;

    }

    return 0;

}




    

zju 1003. Emergency (25)


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 衡阳市| 泌阳县| 固原市| 肥西县| 微山县| 沧源| 本溪市| 武乡县| 上栗县| 张北县| 扎鲁特旗| 怀来县| 思南县| 盈江县| 多伦县| 武夷山市| 防城港市| 浦城县| 浦北县| 夏邑县| 灯塔市| 普兰店市| 山西省| 扎赉特旗| 北辰区| 嘉善县| 清河县| 邮箱| 宁津县| 明水县| 荔浦县| 镇雄县| 岐山县| 当阳市| 延长县| 申扎县| 象州县| 永修县| 丰宁| 建水县| 十堰市|