1003. Emergency (25)

#include "stdafx.h"
#include <iostream>
#include <vector>using namespace std;struct node
{int next, length;
};vector<node> v[510];
int team[510], vis[510], minlength = 10000000, maxteam = -1, pathnum = 0;void dfs(int cur, int curlength, int curteam, int des)
{if(cur == des){if(curlength < minlength){pathnum = 1;minlength = curlength;maxteam = curteam;}else if(curlength == minlength){pathnum++;if(curteam > maxteam){maxteam = curteam;}}return;}int i, size = v[cur].size(), next, nextlength, nextteam;for(i = 0; i < size; i++){next = v[cur][i].next;nextlength = v[cur][i].length + curlength;nextteam = curteam + team[next];if(vis[next] == 0 && nextlength <= minlength){vis[next] = 1;dfs(next, nextlength, nextteam, des);vis[next] = 0;}}
}int main()
{int n, m, c1, c2;scanf("%d%d%d%d", &n, &m, &c1, &c2);int i;for(i = 0; i < n; i++){scanf("%d", &team[i]);}int a, b;node nod;for(i = 1; i <= m; i++){scanf("%d%d%d", &a, &b, &nod.length);nod.next = b;v[a].push_back(nod);nod.next = a;v[b].push_back(nod);}vis[c1] = 1;dfs(c1, 0, team[c1], c2);printf("%d %d\n", pathnum, maxteam);system("pause");return 0;
}