L2-001|L2-001 紧急救援
#include
using namespace std;
const int N = 500+5;
int aid[N];
bool flag[N];
int mind[N];
int path[N];
int cnt[N];
int num[N];
typedef pair pii;
vector graph[N];
vector U,V,W;
priority_queue,greater > pq;
void getAnswer(int n, int m,int s,int t){
memset(mind,127,sizeof(mind));
memset(flag,0,sizeof(flag));
memset(path,-1,sizeof(path));
while(!pq.empty())
pq.pop();
for(int i =0 ;
i<=n;
++i)
graph[i].clear();
for(int i=0;
ifirst;
int w = it->second;
if(mind[u] +w< mind[v]){
num[v] = num[u];
mind[v] = mind[u] + w;
cnt[v] = cnt[u] + aid[v];
path[v] = u;
pq.push(make_pair(mind[v],v));
}else if ( mind[u] + w == mind[v]){
if(cnt[v]< cnt[u] + aid[v]){
cnt[v] = cnt[u] + aid[v];
path[v] = u;
}
num[v] += num[u];
}
}
}
}}
void dfs(int s,int v){
if(v == s)
printf("%d",s);
else{
dfs(s,path[v]);
printf(" %d",v);
}
}
int main()
{
int n,m,s,t;
cin>>n>>m>>s>>t;
for(int i=0;
i>aid[i];
for(int i=0;
i>u>>v>>w;
U.push_back(u);
V.push_back(v);
W.push_back(w);
}
getAnswer(n,m,s,t);
printf("%d %d\n",num[t],cnt[t]);
//dfs(s,t);
stack sta;
sta.push(t);
while(sta.top() != s){
sta.push(path[sta.top()]);
}
//cout<
【L2-001|L2-001 紧急救援】真是万事开头难。
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 告别无效忙碌、低效生活，“重要”“紧急”四象限法则轻松搞定
- 紧急通知，活动无效
- 《紧急救援》的隐藏剧情，我帮你们找出来了
- 心源性休克紧急抢救7大要点
- 关于紧急扩散寻找相关人员的通知
- 阴性！疾控紧急检查黄沙71个涉三文鱼样品
- 乌鲁木齐多渠道解决群众诉求|乌鲁木齐多渠道解决群众诉求 紧急事项4小时内妥善处理并回复处理结果
- 丹麦因生蚝泛滥官方微博紧急求救，中国网友（让我们来）
- 冬日暖阳！HFish蜜罐获湖北省咸宁市紧急医疗救援中心实名感谢
- 紧急提醒！这些微信好友请速删除！